I need to formulate a conditional constraint for a binary variable z defined as:
$z_{i,j,k}$, $\ \ i=1:10 \ , \ j=1:5 \ , \ k=1:3$
If any $z_{i,j,3} = 1$ then $z_{i,j,1} + z_{i,j,2} = 0 \ \ \forall i,j$
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
How about $z_{i,j,1} + z_{i,j,2} \leq 2 \cdot (1 - z_{i,j,3}) \quad \forall i,j$ ?
For more context, I refer you to this excellent self-answer by user D.W. on CS.SX, which includes a link to a helpful gallery of such common "building blocks", all with practical examples stated in prose.
-
1
-
$\begingroup$ For a tighter formulation, see this answer. $\endgroup$– RobPrattMay 20, 2020 at 13:20
-
$\begingroup$ @RobPratt mind to add the tighter formulation as its own answer? As a OR user, I am usually satisfied once my formulation cuts away all undesired integer/binary solutions (and the solver converges quickly enough). $\endgroup$– ojdoMay 20, 2020 at 13:44
$\begingroup$
$\endgroup$
For simplicity, I will omit the $i$ and $j$ subscripts. Rewriting your logical proposition in conjunctive normal form somewhat automatically yields two linear constraints: \begin{equation} z_3 \implies (\neg z_1 \land \neg z_2) \\ \neg z_3 \lor (\neg z_1 \land \neg z_2) \\ (\neg z_3 \lor \neg z_1) \land (\neg z_3 \lor \neg z_2) \\ ((1- z_3) + (1- z_1) \ge 1) \land ((1- z_3) + (1- z_2) \ge 1) \\ (z_3 + z_1 \le 1) \land (z_3 + z_2 \le 1) \end{equation} Note that the big-M constraint $$z_1 + z_2 \le 2(1-z_3)$$ is weaker, being an aggregation of the previous two constraints. For example, the big-M constraint does not cut off $z=(3/4,1/4,1/2)$.
