0
$\begingroup$

I want to write a constraint with ORs in a MILP. In particular, the following:

$$x \ge c \lor x \le -c \lor x=0,$$

where $c$ is just a real number.

Can anyone give me some hints?

$\endgroup$
-1
$\begingroup$

Tough. You are leaving linear programming.

Solve the problem without these equations and with no restriction for the sign of x. If by coincidence x matches one of the conditions, you are done. Otherwise you will need to solve the problem with one of these equations added.

Calculate how much changing x by eps changes the optimal solution. With that guess how much adding x=0, x>=c, or x<=-c would affect the optimal solution. Add the equation that seems to cause the least damage and solve with an optimal goal function G. Then try adding each of the other equations, with an additional restriction goal >= G.

You could have just tried adding each equation in turn and solving, but this way you might find quicker that one condition can’t lead to an optimal solution. For example if c=100 and your optimal solution was x=80, you can add x>=100, optimise , and you can likely show easy that x=0 or x<= -100 will lead to a worse outcome.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't see how this is correct, and I don't see the point in doing this since logical ors can clearly be formulated in MILP. $\endgroup$ – Laakeri Apr 30 at 5:56
  • $\begingroup$ @Laakeri, makes sense... but to be fair, the question body & title are inconsistent about whether the question is asking about MILP or LP. $\endgroup$ – D.W. Apr 30 at 7:50
  • $\begingroup$ @Laakeri So what’s incorrect? Basic method for integer programming, with lots of other applications. $\endgroup$ – gnasher729 Apr 30 at 13:02
  • 1
    $\begingroup$ I see now, this is the branch and bound method for integer programming. Maybe not worth a downvote, but I still think that the answer is probably not useful for the asker since writing an ILP solver by yourself is not realistic compared to writing an ILP encoding of a constraint. $\endgroup$ – Laakeri May 1 at 5:40

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.