4
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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 at 13:08
  • $\begingroup$ For a tighter formulation, see this answer. $\endgroup$ – RobPratt May 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 at 13:44
6
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.