Forbidden range for a linear programming variable 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
 A: 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.
A: 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$
