5
$\begingroup$

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.

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

3 Answers 3

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Dec 14, 2022 at 7:42
10
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Dec 12, 2022 at 10:18
  • $\begingroup$ @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$. $\endgroup$
    – Kuifje
    Dec 12, 2022 at 10:23
  • $\begingroup$ ok I got your point. I presumed, when the summation is not equal to 2, δ=0 is also desired (which is not stated). $\endgroup$ Dec 12, 2022 at 10:33
  • $\begingroup$ +1 for CNF, but it would be good to explicitly specify the two different values for $M$. $\endgroup$
    – RobPratt
    Dec 12, 2022 at 14:42
  • $\begingroup$ yes inded, good idea ! $\endgroup$
    – Kuifje
    Dec 12, 2022 at 15:27
2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Glad to see CNF, but your final proposition is wrong, and your linear constraints are infeasible when $\delta=0$. $\endgroup$
    – RobPratt
    Dec 12, 2022 at 14:37
  • $\begingroup$ @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$? $\endgroup$
    – A.Omidi
    Dec 12, 2022 at 16:12
  • 1
    $\begingroup$ The error is in the last step of CNF. $\endgroup$
    – RobPratt
    Dec 12, 2022 at 16:30
  • $\begingroup$ @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. $\endgroup$
    – A.Omidi
    Dec 12, 2022 at 16:47
  • $\begingroup$ Yes, that is correct, but the same property does not hold for atmost(1) and atleast(3). $\endgroup$
    – RobPratt
    Dec 12, 2022 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.