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

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.

• Is $x_i$ also $\in$ $\{0, 1\}$? Dec 12, 2022 at 8:50
• Please confirm whether you really want only $\implies$ or instead want $\iff$. Dec 12, 2022 at 14:56

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

• what I found cool with this solution is that with the second constraint you basically deal with both $\delta, y_2$ : forcing them to 1 when it's needed Dec 14, 2022 at 7:42

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

• Say y1=1, meaining first constraint is active, what blocks δ =1? (if δ is in obj. with minimization, it would work) should there be additional 2 constraints like δ+y1<=1 and δ+y2<=1... or even better how about δ+y1+y2=1 so only one of them will be active. Dec 12, 2022 at 10:18
• @EvrenGuney In this case, nothing prevents $\delta$ from taking value 1. Note that the implication is the other way around, OP did not specify something like $X \implies \delta=0$. Dec 12, 2022 at 10:23
• ok I got your point. I presumed, when the summation is not equal to 2, δ=0 is also desired (which is not stated). Dec 12, 2022 at 10:33
• +1 for CNF, but it would be good to explicitly specify the two different values for $M$. Dec 12, 2022 at 14:42
• yes inded, good idea ! Dec 12, 2022 at 15:27

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.

• Glad to see CNF, but your final proposition is wrong, and your linear constraints are infeasible when $\delta=0$. Dec 12, 2022 at 14:37
• @RobPratt, Thanks Dr. Pratt for your hint. Besides the way Kuifje uses the indicator constraints as a standard way, I would like to try $\text{exactly}$ CNF form to do that. Would you please, say the wrong part comes in the CNF format or in two last inequalities? Is not the first part of the last CNF expression translated as $\sum x_i -M.\delta \leq 1$? Dec 12, 2022 at 16:12
• The error is in the last step of CNF. Dec 12, 2022 at 16:30
• @RobPratt, thanks. As far as I know, $(\text{atleast(1)}_i x_i \lor \delta$ can be written as $(\text{atleast(1)}_i (x_i \lor \delta)$. If not, would you please, write the correct form. Dec 12, 2022 at 16:47
• Yes, that is correct, but the same property does not hold for atmost(1) and atleast(3). Dec 12, 2022 at 16:50