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$

2 Answers 2

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.

$\endgroup$
3
  • 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$ May 20, 2020 at 13:08
  • $\begingroup$ For a tighter formulation, see this answer. $\endgroup$
    – RobPratt
    May 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$
    – ojdo
    May 20, 2020 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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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