1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ but what if x1 is bigger than 2 and x2 is bigger than 3? Then z would be both 0 and 1 by your formulation which doesn't make sense. Shouldn't z be defined by either one variable or the other? $\endgroup$ – BrianW Jan 30 '17 at 1:23
  • $\begingroup$ Suppose that $x_{1}$ is bigger than 2 and $x_{2}$ is bigger than 3. Since $z$ is a binary variable so it is constrained to be either 0 or 1. If $z=0$, then both constraints are satisfied. If $z=1$, then both constraints are satisfied. In this case it doesn't matter whether $z$ is 0 or 1. $\endgroup$ – Brian Borchers Jan 30 '17 at 3:19
  • $\begingroup$ I've updated my question and I think I could have found a solution. Would you care to look at it? Thanks! @BrianBorchers $\endgroup$ – BrianW Jan 31 '17 at 22:22
  • $\begingroup$ Your solution doesn't exclude the strip where $x_{1}=2$ and $x_{2}<3$. For example, try $x_{1}=2$, $x_{2}=1$, $z=1$. Your solution gives the same feasible region as my solution above and doesn't satisfy the original requirement stated in your question. $\endgroup$ – Brian Borchers Jan 31 '17 at 22:50
  • $\begingroup$ If instead of 3 in my $y$ constraint I put 2.9999, would that fix that issue? I understand that it won't be 100% accurate, but for programming purposes it would get me close enough to my optimal solution I think. $\endgroup$ – BrianW Feb 1 '17 at 1:02

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.