I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed.

Do you know a way to express this constraint in a linear program, in a way that it can be solved using an unmodified simplex implementation ?

For example this constraint : $x_1 \geq 4$ or $x_1 = 0$.

Typical relation between all constraints in a linear program is AND. Here this is an OR between two constraints.

Note : I need to solve problems having multiple variables like this in a computationally efficient way


  • 1
    $\begingroup$ This can't be done with strict linear programming. If you're willing to employ binary variables and branch and bound, you can do this. $\endgroup$ – Michael Grant Jun 27 '14 at 14:53
  • $\begingroup$ I were hopping I could use a home made linear simplex solver with some tricks :(. $\endgroup$ – infiniteLoop Jun 27 '14 at 17:25
  • $\begingroup$ I'm afraid not. It's not linear. There is no way to avoid some sort of branching approach where you decide which "side" of the disjunction to try at each stage. $\endgroup$ – Michael Grant Jun 27 '14 at 17:31
  • $\begingroup$ Thanks. That's bad news. I wish there was some tricks, like the ones used to compute absolute value or min between variables $\endgroup$ – infiniteLoop Jun 27 '14 at 17:36

Here's the bad news: you can't do this with a straight-up linear program.

Here's the good news: you can do this with an integer linear program.

Introduce an additional binary decision variable $z$. Let $z=0$ whenever $x=0$ and $z=1$ whenever $x\ge 4$. Furthermore, pick an arbitrarily large number, call it $M$, such that $M$ can not bound your $x$ variable too soon(e.g. if your problem data is on the order of $10^2$, pick $M=10^5$ or something). Now add the following constraints to your problem:

$$ x \ge 4z \\ x \le Mz $$

If $z=0$, the constraints force $x=0$. If $z=1$ the constraints force $x \ge 4$ (since $M$ is large enough by definition).

In general, the modeling issue is capturing a situation like this: $$x = 0 \lor x\in[a,b], \quad0<a<b<\infty$$ $x$ is called a semicontinuous variable, and the trick that I've shown you above extends naturally to the following pair of constraints: $$ x \ge az \\ x \le bz $$

Unless you are coding the algorithm yourself, be aware that most commercial solver packages can handle semicontinuous variables internally (by doing the constraint modeling internally and branching on $z$). Read the appropriate documentation for the syntax.

  • $\begingroup$ Thanks for your answer and the term "semicontinuous" that describe my variable. Unfortunately I have a home made implementation of the two-phase simplex and I were hopping I could use it with some tricks :(. $\endgroup$ – infiniteLoop Jun 27 '14 at 17:24
  • $\begingroup$ @trinita Nope, you will have to also implement a home-brew version of a branch-and-bound scheme in order to accommodate semi-continuity. Honestly, you're better off examining the source code of some open-source projects such as GLPK or COIN-OR. $\endgroup$ – baudolino Jun 27 '14 at 17:43
  • $\begingroup$ @trinita BTW, welcome to Math.SE. If you like this answer and feel it adequately captures your question, please upvote and accept. $\endgroup$ – baudolino Jun 27 '14 at 17:47
  • $\begingroup$ Ok I will look into branch-and-bound method $\endgroup$ – infiniteLoop Jun 27 '14 at 17:53

Another possible constraint:

$y_1(x_1-4-z_1)+(1-y_1)\cdot x_1=0$

$y_1 \in \{0,1 \}, z_1 \geq 0$

  • $\begingroup$ This is not linear programming, cause there is a product between variables and also binary variables. $\endgroup$ – infiniteLoop Jun 27 '14 at 17:29
  • $\begingroup$ You are right. As baudolina has said already, you can´t mangage the problem with a straight-up linear program. It was only another (simple) suggestion. $\endgroup$ – callculus Jun 27 '14 at 17:37
  • $\begingroup$ Ok thanks for the suggestion $\endgroup$ – infiniteLoop Jun 27 '14 at 17:45
  • $\begingroup$ You are welcome. If you are looking for a optimization program try Lingo. The "coding language" is quiet simple. And it is for free for a certain maximum number of variables. $\endgroup$ – callculus Jun 27 '14 at 18:52

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.