I am trying to write out a linear program, and I am stuck on how to formulate one of the constraints I need.
I need to write a constraint that says:
"If $x_1 \le 2$ then $y\ge3$."
I assume I need to use a Big M method approach, but I can't figure out anything past that.
UPDATE
I have made a truth table and set up the following variables and constraints:
Let $z =0$ if $x\le 2$ and $z=1$ if $x\gt 2$
$x-2\le Mz$
$2-x\le M(1-z)$
$3-y \le Mz$
If I am doing my truth table correctly, of the 8 possible combinations, I should allow $x\le2, y\ge3, z=0$ and $x>2, y<3, z=1$ and $x>2, y\ge 3, z=1$. I think that my constraints do this. Is this a viable solution?
Best Answer
First, note that the feasible region associated with your constraint is non-convex. Thus it is not possible to formulate this constraint using linear programming alone.
Typically, constraints like these are formulated in mixed integer programming by using 0-1 binary variables (the integer aspect of the formulation) to turn constraints on and off. Using this approach, it is possible to write constraints for feasible regions that can be expressed as finite unions or intersections of closed convex sets that can each be represented by linear inequality (less than or equal to) constraints. As you've mentioned, it is necessary to include "big-M" constants in the constraints. The resulting feasible region for the mixed integer linear programming (MILP) problem is always closed.
Your feasible set consists of the union of the set of points with $x_{1}>2$ and the set of points with $x_{2} \geq 3$. Unfortunately, because the edge of the feasible region where $x_{1}=2$ and $x_{2} <3$ is not included in the feasible region, your desired feasible region is not closed, and thus it isn't possible to formulate the problem using the approach that I've mentioned.
If you are willing to include this edge where $x_{1}=2$ and $x_{2}<3$ in the feasible region, then this can be accomplished.
Start by adding a 0-1 variable $z$ where $z=0$ if $x_{1} \geq 2$ and $z=1$ is $x_{2} \geq 3$. Write the constraints as
$x_{1} + Mz \geq 2$
$x_{2} + M(1-z) \geq 3$
Here $M$ is a large positive constant. Since the first constraint would be ineffective if $x_{1}$ was more negative than $-(M-2)$, you must ensure $M$ is sufficiently large. However, it's a good idea to keep $M$ as small as possible to avoid numerical issues in the solution of the problem.