MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$

Question

I want to formulate a MIP constraint such that : $$\sum_{i=1}^nx_i = 2 \implies \delta = 1$$ $x_i, \delta \in \{0, 1\}$.
My problem is that delta should be one when this sum is exactly 2 and not greater or less than.

Answer 1

Assuming $x_i$ variables are binary, the contraposition reads as follows: $$ \delta = 0 \implies \left( \sum_{i=1}^n x_i \le 1 \right)\vee \left( \sum_{i=1}^n x_i \ge 3 \right) $$ Define a binary variable $y_1$ that takes value $1$ if and only if $\sum_{i=1}^n x_i \le 1$ and another one $y_2$ that takes value $1$ if and only if $\sum_{i=1}^n x_i \ge 3$, such that in conjunctive normal form: $$ \neg \delta \implies y_1 \vee y_2 $$ $$ \delta \vee y_1 \vee y_2 $$ $$ \delta +y_1 +y_2 \ge 1 $$ So in summary: $$ \sum_{i=1}^n x_i \le 1+M_1(1-y_1) \\ \sum_{i=1}^n x_i \ge 3-M_2(1-y_2) \\ \delta +y_1 +y_2 \ge 1 \\ x_i,y_i,\delta \in \{0,1\} $$

Since $0\le \sum_{i=1}^nx_i\le n$, you can use values $M_1=n-1$ and $M_2=3$.

Answer 2

Assuming you also want to enforce the converse, here’s another approach that uses the same additional binary variables $y_1$ and $y_2$ as in @Kuifje’s answer. $$ y_1+\delta+y_2=1\\ 0y_1+2\delta+3y_2\le \sum_{i=1}^n x_i \le 1y_1+2\delta+ny_2 $$ If you prefer, you can think of $y_1$ as a slack variable and eliminate it, yielding $$ \delta+y_2\le 1\\ 2\delta+3y_2\le \sum_{i=1}^n x_i \le 1+\delta+(n-1)y_2 $$

Answer 3

As the expression is totally boolean form and based on the logic modeling, the mentioned if-then would be:

$$ \text{exactly(2)}_i x_i \implies \delta = 1 $$ $$ \text{atleast(2)}_i x_i \land \text{atmost(2)}_i x_i \implies \delta = 1$$ $$ \lnot (\text{atleast(2)}_i x_i \land \text{atmost(2)}_i x_i) \lor \delta$$ $$ (\text{atmost(2-1)}_i x_i \lor \text{atleast(2+1)}_i x_i) \lor \delta$$ $$ (\text{atmost(1)}_i x_i \lor \text{atleast(3)}_i x_i) \lor \delta$$ $$ (\sum_{i=1}^n x_{i} \leq 1) \lor ((\sum_{i=1}^n x_{i} \geq 3) \lor \delta$$

By introducing the auxiliary variables, the last line would be: $$ z_{1} + z_{2} + \delta \geq 1 $$

Now, the linearization can be written as: $$ z_{1} + z_{2} + \delta \geq 1 $$ $$ \sum_{i=1}^n x_{i} - M_1.z_{1} \geq 0 $$ $$ \sum_{i=1}^n x_{i} + M_2.z_{2} \leq UB$$

Also, if one would like to see how the original expression can be converted to a CNF which is finally translated to the math without auxiliary binary variables, please took a look at this link and useful answer by @RobPratt.