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
Thanks
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.