Modeling the sum of binary variables

Question

Suppose $x_{1},x_{2}, \cdots ,x_{n}$ are binaries.

I would like to model the following:

IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 2$ THEN $x_{1} + x_{2} = 2$

IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 3$ THEN $x_{1} + x_{2} + x_{3}= 3$

and so on.

Is there a better way than asking for the following

$(x_{1} \ge 1) \lor (x_{1} + x_{2} \ge 2) \lor (x_{1} + x_{2} + x_{3} \ge 3) \cdots $, which then requires the introduction of additional binaries?

I think you need another clause in the disjunction: $\sum_{i=1}^n x_i = 0$. Otherwise, $x_1=1$ is forced. — RobPratt, May 12, 2020 at 20:35

RobPratt · Accepted Answer · 2020-05-12 19:50:58Z

5

Does $x_i \ge x_{i+1}$ do what you want?

answered May 12, 2020 at 19:50

RobPratt

30.5k1 gold badge43 silver badges83 bronze badges

$\begingroup$ That's genius... $\endgroup$
– Oguz Toragay
May 12, 2020 at 19:58
$\begingroup$ Thank you Rob. This is what I already have implemented. I hoped, that is the purpose of the question, I can do something without having to wait for the end of the optimisation run. I mean, if I have the constraint x1 + x2 + x3 => 2 then in a relaxation it can be satisfied as (x1,x2,x3) = (0.8,0.7,0.5), which satisfies the requirement x(i) => x(i+1) but not x1+x2=2. $\endgroup$
– Clement
May 12, 2020 at 20:18
$\begingroup$ Looks like the simple formulation already yields the integer hull, so you will not get anything stronger unless you consider the other constraints in your model. $\endgroup$
– RobPratt
May 12, 2020 at 20:32
$\begingroup$ Then I can stop looking for something better. Thank you again Rob. $\endgroup$
– Clement
May 12, 2020 at 21:00

Add a comment |

1 Answer 1