In linear programming, how can I specify a lower bound for the positive entries in the decision vector

Question

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.

Answer 1

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)

Answer 2

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$$

Answer 3

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]$.