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$


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$ Oooh -- that is a great answer on CS.SX. On OR.SE, there's this one and this one but the CS one is quite comprehensive. $\endgroup$
    – LarrySnyder610
    May 20 '20 at 13:08
  • $\begingroup$ For a tighter formulation, see this answer. $\endgroup$
    – RobPratt
    May 20 '20 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$
    – ojdo
    May 20 '20 at 13:44

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.