Conditional Constraint in MIP

Question

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$

ojdo · Answer 1 · 2020-05-20T12:41:13.273

6

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.

edited May 20 '20 at 12:41

answered May 20 '20 at 11:11

ojdo

165
1
6

1

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. – LarrySnyder610 May 20 '20 at 13:08
For a tighter formulation, see this answer. – RobPratt May 20 '20 at 13:20
@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). – ojdo May 20 '20 at 13:44

score 6 · Answer 2 · answered May 20 '20 at 14:11

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

Conditional Constraint in MIP

2 Answers2