6
$\begingroup$

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.

$\endgroup$
0
10
$\begingroup$

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

$\endgroup$
1
  • 6
    $\begingroup$ 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\}$. $\endgroup$ – RobPratt Feb 5 at 19:59

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.