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?

  • $\begingroup$ I think you need another clause in the disjunction: $\sum_{i=1}^n x_i = 0$. Otherwise, $x_1=1$ is forced. $\endgroup$ – RobPratt May 12 '20 at 20:35
  • $\begingroup$ Yes, you are right! $\endgroup$ – Clement May 12 '20 at 21:01

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

  • $\begingroup$ That's genius... $\endgroup$ – Oguz Toragay May 12 '20 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 '20 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 '20 at 20:32
  • $\begingroup$ Then I can stop looking for something better. Thank you again Rob. $\endgroup$ – Clement May 12 '20 at 21:00

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.