I have the following questions. I have the variables $a_{bj}$ and $c_{bj}$, both binary. I now want the sum of both variables to be zero, in case the third binary variable $d_{bj}$ takes the value 1. However, $d_{bj}$ can only take the value 1 once, but the sum must always be zero in all subsequent periods. How does this work?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ What index represents period? $\endgroup$RobPratt– RobPratt2024-11-12 22:23:13 +00:00Commented Nov 12, 2024 at 22:23
-
$\begingroup$ @RobPratt $j$ represents the period $\endgroup$manofthousandnames– manofthousandnames2024-11-13 08:33:20 +00:00Commented Nov 13, 2024 at 8:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
Let $e_{bj}=\sum_{t\le j} d_{bt}$, which is binary by assumption. You want to enforce the logical implication $$e_{bj} \implies \lnot a_{bj} \land \lnot c_{bj}.$$ Rewriting in conjunctive normal form somewhat automatically yields linear constraints: $$ \lnot e_{bj} \lor (\lnot a_{bj} \land \lnot c_{bj}) \\ (\lnot e_{bj} \lor \lnot a_{bj}) \land (\lnot e_{bj} \lor \lnot c_{bj}) \\ (1-e_{bj} + 1-a_{bj} \ge 1) \land (1-e_{bj} + 1-c_{bj} \ge 1) \\ (e_{bj} + a_{bj} \le 1) \land (e_{bj} + c_{bj} \le 1) $$ That is, \begin{align} e_{bj} + a_{bj} \le 1 \\e_{bj} + c_{bj} \le 1 \end{align}
-
$\begingroup$ Thank you. sadly I am not to familiar with translating this to a regular system of constraints. How would they look like? $\endgroup$manofthousandnames– manofthousandnames2024-11-13 08:16:16 +00:00Commented Nov 13, 2024 at 8:16
-
$\begingroup$ @manofthousandnames, the final line is the result, Rob was just showing the steps to get to it. The constraints to add are $d_{b_j} + a_{b_j} \leq 1$ and $d_{b_j} + c_{b_j} \leq 1$. $\endgroup$João Dionísio– João Dionísio2024-11-13 09:52:07 +00:00Commented Nov 13, 2024 at 9:52
-
$\begingroup$ I see, but how would that work f.e. $d_{bj}$ takes on the value of 1 in period $j=10$, leading to $d_{b,11}=0$ again. Then in period 10 these constraints for $a_{bj}, c_{bj}$ to zero, but not in period 11, or am I wrong? $\endgroup$manofthousandnames– manofthousandnames2024-11-13 10:29:16 +00:00Commented Nov 13, 2024 at 10:29
-
$\begingroup$ @manofthousandnames I updated my answer to account for the clarification of the question. $\endgroup$RobPratt– RobPratt2024-11-13 13:50:08 +00:00Commented Nov 13, 2024 at 13:50
-
$\begingroup$ @RobPratt Can you recommend any literature that helps me learning transformating logical implications to conjunctive normal form and then to linear constraints? $\endgroup$mingabua– mingabua2024-11-14 09:16:33 +00:00Commented Nov 14, 2024 at 9:16
$\begingroup$
$\endgroup$
3
If I understood correctly, you're looking to model this
t 1 2 3 4 5 6 7 8 ...
a[t] 0 1 0 1 0 0 0 0 ...
c[t] 0 0 1 1 0 0 0 0 ...
d[t] 0 0 0 0 1 0 0 0 ...
Both $a$ and $c$ are free when $d = 0$. As soon as $d$ takes value 1, both variables take value $0$ for all subsequent time-steps. Under the hypothesis that $d$ takes value 1 only once, you can model your logic by
\begin{equation} a_t + c_t \leqslant 2\cdot(1 - \sum_{t' = 1}^t d_{t'}), \quad \forall t \geqslant 1, \end{equation}
The behavior of $d$ is similar to that of a step variable.
-
$\begingroup$ This is correct (+1), and you can alternatively use a stronger disaggregated formulation $a_t\le 1-\sum_{t'\le t} d_{t'}$ and $c_t\le 1-\sum_{t'\le t} d_{t'}$. $\endgroup$RobPratt– RobPratt2024-11-13 15:51:23 +00:00Commented Nov 13, 2024 at 15:51
-
$\begingroup$ @RobPratt Thank. May I ask why yours is "stronger"? $\endgroup$manofthousandnames– manofthousandnames2024-11-13 19:52:33 +00:00Commented Nov 13, 2024 at 19:52
-
$\begingroup$ @manofthousandnames Summing the disaggregated version yields the aggregated version, so the disaggregated version is at least as strong. To see that it is actually stronger, consider $\sum_{t'\le t} d_t=1/2, a_t=1, c_t=0$, which satisfies the aggregated version but not the disaggregated version. $\endgroup$RobPratt– RobPratt2024-11-13 20:02:26 +00:00Commented Nov 13, 2024 at 20:02
$\begingroup$
$\endgroup$
1
You basically want to have constraints to be active once a binary variable $x_t$ assumes $x_t=1$ for some $t$.
My simplistic approach would be to introduce a new binary variable $y_t$ that is 1 once $x_t=1$, and 0 before. I.e., it follows the pattern:
x[t] 0 0 1 0 0
y[t] 0 0 1 1 1
This can be modeled recursively as $$y_t=\max(x_t,y_{t-1})$$ Some solvers support this directly, but this can also be linearized quite easily:
$$\begin{aligned}& y_t \ge x_t\\ & y_t \ge y_{t-1}\\ & y_t \le x_t +y_{t-1} \\ & y_0=0 \end{aligned}$$
Here, I assume that $x_t$ starts at $t=1$.
Once you have this $y_t$, life is easy. You can use it in constraints that need to hold when $x_t=1$ and later.
Notes:
- If $y_t$ is only used to activate constraints when $y_t=1$, you can drop the $y_t \le x_t +y_{t-1}$ constraint.
- The $y_t$ variables can be relaxed to be continuous.
- This recursive approach minimizes the number of nonzero elements at the expense of additional variables and constraints. Solvers often like larger but sparser models.
Update. As Rob Pratt helpfully indicated, it is better to use: $$y_t = x_t +y_{t-1}$$
-
2$\begingroup$ Because $\sum_t x_t \le 1$, you can get by with just $y_t=x_t+y_{t-1}$, which is both simpler and stronger. $\endgroup$RobPratt– RobPratt2024-11-13 14:02:03 +00:00Commented Nov 13, 2024 at 14:02