1
$\begingroup$

For decision vector $x$, I have a constraint that either $x\leq0$ or $x\geq5$, that is, all positive entries must be at least 5.

Is there a way to cast this under LP? The problem is already a mixed-integer program, so introducing binary/integer auxiliary variables are ok, if necessary.

I tried to use the usual positive/negative split trick

$$y - z = x$$

and set

$$y\geq5, z\geq0$$

But this fails here since I'm not minimising $y$ or $z$, so the solution gets $y=5$ and $z=1$ to bypass the constraint.

$\endgroup$
1

3 Answers 3

3
$\begingroup$

You have a disjunctive inequality which may be expressed as $[z=0,x \leq 0] \vee [z=1,x \geq 5]$. This is non-convex, so cannot be expressed as an LP. But as you suggest, there is a way to formulate it as a MILP. One method is the big-M formulation. In this case, it takes the form of two constraints $x \leq 0 + Mz$ and $x \geq 5 - M(1-z)$, where $M$ is a large positive constant. In theory you would choose the largest representable integer. In practice, however, it is recommended that you choose $M$ to be ``sufficiently large, but not too large’’. Choosing an unnecessarily large value can cause difficulty for the MILP solver. If you are sure the optimal value of $x$ is in the range $[-100,100]$, for example, then it is sufficient to let $M=100$. Note also that you may define the constraints as $x \leq 0 + M_1z$ and $x \geq 5 - M_2(1-z)$ where $M_1 \neq M_2$ and you expect the optimal value of $x$ to be in the range $[-M_1,M_2]$.

(jf328: edited to fix a typo)

$\endgroup$
2
$\begingroup$

This is a disjunctive constraint. Some optimization modeling systems/languages and solvers allow you to directly specify constraints as disjunctive, and they will take care of it for you.

If not, this can be handled by big M Modeling.

Introduce a binary variable $b$.

Let $L$ = lower bound of $x$.

Let $U$ = upper bound of $x$.

Include the constraints: $$x \le U(1-b)$$ $$x \ge 5 +(L-5)b$$

$\endgroup$
0
$\begingroup$

Mark’s answer appeared while I wa composing my answer. Mark’s use of $U$ and $L$ is, IMO, clearer than my names $M_1$ and $M_2$, and allowed me to see that the range $[-M_1,M_2]$ is incorrect. I should have written $[-M_2,M_1]$.

$\endgroup$
1
  • $\begingroup$ You can edit your previous answer, rather than posting a new answer for the correction. That would be the preferred way actually. $\endgroup$ Jan 6 at 2:30

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.