3
$\begingroup$

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?

$\endgroup$
2
  • $\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, 2020 at 20:35
  • $\begingroup$ Yes, you are right! $\endgroup$
    – Clement
    May 12, 2020 at 21:01

1 Answer 1

5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ That's genius... $\endgroup$ 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

Your Answer

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

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