# ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied

Consider several Integer (0/1) ILP variables, i.e., Boolean variables, $$x_i$$'s. Consider an ILP constraint $$x_1 + x_2 + x_3 \geq 1$$ and another constraint $$x_4 + x_5 + x_6 \geq 1$$. I would like to represent that exactly one such constraint is satisfied, ie. if $$x_1 + x_2 + x_3 \geq 1$$ is satisfied, the constraint $$x_4 + x_5 + x_6 \geq 1$$ should not be satisfied and vice versa. How can such a constraint be represented? In the example, there are two constraints, how can it be generalized to any number of similar constraints? Variables are unique across constraints, i.e., variables which occur in the first constraint do not occur in the other constraints.

## 1 Answer

You can add an extra binary that equals $$1$$ if and only if the first constraint is satisfied:

\begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align}

If $$\delta=1$$, the first two constraints become: $$1 \le x_1+x_2+x_3 \le 3$$ And the last two: $$0 \le x_4+x_5+x_6 \le 0$$

And likewise the other way around if $$\delta=0$$.

You can easily generalize this approach by adding as many binaries as necessary (one for each pair of constraints), and by adapting the "big-M" values ($$3$$ in the above example).

• You can get a tighter formulation by disaggregating the $\le$ constraints as $x_i \le \delta$ for $i\in\{1,2,3\}$ and $x_i \le 1 - \delta$ for $i\in\{4,5,6\}$. – RobPratt Feb 5 at 19:59