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

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.

• I wouldn't say this is off-topic here, but or.stackexchange.com is a better fit. Jan 4 at 11:15

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)

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

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

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