Integer programming model (alternating constraints)

[fishturtle1]

Homework Statement

Formulate as a mixed integer programming problem but do not solve. Maximize $x_1 + x_2$ subject to $2x_1 + 3x_2 \le 12$ or {$3x_1 + 4x_2 \le 24$ and $-x_1 + x_2 \ge 1$} $x_1, x_2 \ge 0$

Homework Equations

The Attempt at a Solution

if the first constraint is met, we have upper bounds $x_1 = 6, x_2 = 4$,
so $2x_1 + 3x_2 - 12 \le 2(6) + 3(4) -12 = 12$

if the set of constraints is met, from the first constraint of the set we have upper bounds $x_1 = 8, x_2 = 6$ and from the second constraint of the set we have upper bounds $(-x_1 \ge 1) \rightarrow (x_1 \le -1) \rightarrow x_1 = 0?, x_2$ is not bounded above.

Therefore, for the whole set, we have upper bounds $x_1 = 0, x_2 = 6$

Therefore, $3x_1 + 4x_2 - 24 \le 3(0) + 4(6) - 24 = 0$
and $-x_1 + x_2 - 1 \ge -(0) +(0) - 1 = -1$

So the model is Maximize $x_1 + x_2$
subject to
$2x_1 + 3x_2 - 12 \le 12(1 - y_1)$
$3x_1 + 4x_2 - 24 \le 0(1 - y_2)$
$-x_1 + x_2 -1 \ge -1(1 - y_2)$

$y \space \epsilon${0,1} and $x_i \ge 0$ for all i.

the answer key has $-x_1 + x_2 -1 \ge -7(1 - y_2)$ instead of -1 in my third constraint... where did i go wrong?

 

[Ray Vickson]

Homework Statement

Formulate as a mixed integer programming problem but do not solve. Maximize $x_1 + x_2$ subject to $2x_1 + 3x_2 \le 12$ or {$3x_1 + 4x_2 \le 24$ and $-x_1 + x_2 \ge 1$} $x_1, x_2 \ge 0$

Homework Equations

The Attempt at a Solution

if the first constraint is met, we have upper bounds $x_1 = 6, x_2 = 4$,
so $2x_1 + 3x_2 - 12 \le 2(6) + 3(4) -12 = 12$

if the set of constraints is met, from the first constraint of the set we have upper bounds $x_1 = 8, x_2 = 6$ and from the second constraint of the set we have upper bounds $(-x_1 \ge 1) \rightarrow (x_1 \le -1) \rightarrow x_1 = 0?, x_2$ is not bounded above.

Therefore, for the whole set, we have upper bounds $x_1 = 0, x_2 = 6$

Therefore, $3x_1 + 4x_2 - 24 \le 3(0) + 4(6) - 24 = 0$
and $-x_1 + x_2 - 1 \ge -(0) +(0) - 1 = -1$

So the model is Maximize $x_1 + x_2$
subject to
$2x_1 + 3x_2 - 12 \le 12(1 - y_1)$
$3x_1 + 4x_2 - 24 \le 0(1 - y_2)$
$-x_1 + x_2 -1 \ge -1(1 - y_2)$

$y \space \epsilon${0,1} and $x_i \ge 0$ for all i.

the answer key has $-x_1 + x_2 -1 \ge -7(1 - y_2)$ instead of -1 in my third constraint... where did i go wrong?

You can use $2x_1+3x_2-12 \leq M_1 (1-y)$, $3x_1 + 4x_2 -24 \leq M_2 \,y$ and $-x_1+x_2-1 \geq -M_3\, y$, where $M_1, M_2, M_3>0$ are chosen large enough that constraints $2x_2 + 3 x_2 - 12 \leq M_1$, $3x_1 + 4x_2 - 24 \leq M_2$ and $-x_1 + x_2 -1 \geq -M_3$ are all redundant. It does not really matter a lot what values of the $M_i$ you choose, just as long as they are not much too large: if $M = 20$ will work, do not choose $M = 2,00,000$.

Among the three constraints, the second one $3x_1 + 4x_2 \leq 24$ is the "loosest", giving $x_1 \leq 8$ and $x_2 \leq 6$. Therefore, $2x_1 + 3x_2 \leq 2(8) + 3(6) = 30,$ so we can pick $M_1 = 30-12 = 18$. We have $3x_1 + 4 x_2 \leq 3(8) + 4(6) = 48$, so we can pick $M_2 = 48-24 = 24.$ Finally, $-x_1 + x_2 \geq -8 + 0 = -8;$ thus $-x_1 + x_2 - 1 \geq -9$ is redundant, so we can pick $M_3 = 9$.

With a bit more work we might be able to come up with smaller $M_i$, but I doubt that it is worth worrying about. (It might be worth worrying about if we had $M_1 = 1800$ for example---in a problem where $M_1 = 18$ will do---because that would lead to feasible $(x_1,x_2,y)$ region in the LP relaxation that is long and narrow, thus magnifying the effects of computational roundoff errors and making it harder to distinguish between branches and bounds in a search tree for the integer problem.)
Apparently, your book was able to use $M_3 = 7$ instead of $M_3 = 9$, but as I said, that is not very important in practice.

 

[fishturtle1]

You can use 2x1+3x2−12≤M1(1−y)2x1+3x2−12≤M1(1−y)2x_1+3x_2-12 \leq M_1 (1-y), 3x1+4x2−24≤M2y3x1+4x2−24≤M2y3x_1 + 4x_2 -24 \leq M_2 \,y and −x1+x2−1≥−M3y−x1+x2−1≥−M3y-x_1+x_2-1 \geq -M_3\, y, where M1,M2,M3>0M1,M2,M3>0M_1, M_2, M_3>0 are chosen large enough that constraints 2x2+3x2−12≤M12x2+3x2−12≤M12x_2 + 3 x_2 - 12 \leq M_1, 3x1+4x2−24≤M23x1+4x2−24≤M23x_1 + 4x_2 - 24 \leq M_2 and −x1+x2−1≥−M3−x1+x2−1≥−M3-x_1 + x_2 -1 \geq -M_3 are all redundant. It does not really matter a lot what values of the MiMiM_i you choose, just as long as they are not much too large: if M=20M=20M = 20 will work, do not choose M=2,00,000M=2,00,000M = 2,00,000.

Among the three constraints, the second one 3x1+4x2≤243x1+4x2≤243x_1 + 4x_2 \leq 24 is the "loosest", giving x1≤8x1≤8x_1 \leq 8 and x2≤6x2≤6x_2 \leq 6. Therefore, 2x1+3x2≤2(8)+3(6)=30,2x1+3x2≤2(8)+3(6)=30,2x_1 + 3x_2 \leq 2(8) + 3(6) = 30, so we can pick M1=30−12=18M1=30−12=18M_1 = 30-12 = 18. We have 3x1+4x2≤3(8)+4(6)=483x1+4x2≤3(8)+4(6)=483x_1 + 4 x_2 \leq 3(8) + 4(6) = 48, so we can pick M2=48−24=24.M2=48−24=24.M_2 = 48-24 = 24. Finally, −x1+x2≥−8+0=−8;−x1+x2≥−8+0=−8;-x_1 + x_2 \geq -8 + 0 = -8; thus −x1+x2−1≥−9−x1+x2−1≥−9-x_1 + x_2 - 1 \geq -9 is redundant, so we can pick M3=9M3=9M_3 = 9.

Thanks for the reply.

Since we chose the "loosest" constraint's upper bounds, $U_1 \ge x_1, U_2 \ge x_2$ in constraint 3, that means they are also upper bounds of the first constraint's variables and the third constraint's variables, since an upper bound is just some number that is greater than or equal to all $x_i$ of some set $X$. Then what I did was too much, I can just use the greatest upper bound and apply it to all constraints. Do I understand you?

edit: I am confused.. If we let $M_i$ get bigger or smaller doesn't that mean our set of feasible solutions also changes? And isn't that bad?

 

[Ray Vickson]

Thanks for the reply.

Since we chose the "loosest" constraint's upper bounds, $U_1 \ge x_1, U_2 \ge x_2$ in constraint 3, that means they are also upper bounds of the first constraint's variables and the third constraint's variables, since an upper bound is just some number that is greater than or equal to all $x_i$ of some set $X$. Then what I did was too much, I can just use the greatest upper bound and apply it to all constraints. Do I understand you?

**********************
I think so, but it is not quite that easy if we have mixed signs in the left-hand-sides of the constraints.
***********************

edit: I am confused.. If we let $M_i$ get bigger or smaller doesn't that mean our set of feasible solutions also changes? And isn't that bad?

If we let $M_i$ get bigger, the feasible region for the mixed IP problem remains exactly the same, but the feasible region of the LP relaxation gets larger. If it gets a bit larger that will not matter very much, but making it much, much larger that it needs to be is definitely not advisable.

Generally, there is a tradeoff when modelling such situations: should we spend a lot of time and effort getting nearly the best $M_i$ possible, or should we just go with "reasonable" $M_i$ and then get on with the problem-solving process? Of course, generally speaking, the problem solving process is shorter and more efficient if we use smaller $M_i$, but it is hard to know the exact tradeoff. Remember: in industrial-sized problems like yours we may have hundreds of thousands of variables and tens to hundreds of thousands of constraints, so what looks simple enough in a 2-variable, 3-constraint example might be pretty horrible in a realistic scenario.

 

[fishturtle1]

If we let $M_i$ get bigger, the feasible region for the mixed IP problem remains exactly the same, but the feasible region of the LP relaxation gets larger. If it gets a bit larger that will not matter very much, but making it much, much larger that it needs to be is definitely not advisable.

Generally, there is a tradeoff when modelling such situations: should we spend a lot of time and effort getting nearly the best $M_i$ possible, or should we just go with "reasonable" $M_i$ and then get on with the problem-solving process? Of course, generally speaking, the problem solving process is shorter and more efficient if we use smaller $M_i$, but it is hard to know the exact tradeoff. Remember: in industrial-sized problems like yours we may have hundreds of thousands of variables and tens to hundreds of thousands of constraints, so what looks simple enough in a 2-variable, 3-constraint example might be pretty horrible in a realistic scenario.

That makes sense, thank you.

 

[FactChecker]

Thanks for the reply.

Since we chose the "loosest" constraint's upper bounds, $U_1 \ge x_1, U_2 \ge x_2$ in constraint 3, that means they are also upper bounds of the first constraint's variables and the third constraint's variables, since an upper bound is just some number that is greater than or equal to all $x_i$ of some set $X$. Then what I did was too much, I can just use the greatest upper bound and apply it to all constraints. Do I understand you?

edit: I am confused.. If we let $M_i$ get bigger or smaller doesn't that mean our set of feasible solutions also changes? And isn't that bad?

The point of making the M values large is to get it's constraint out of the way when it is not applicable to the "or" option that is being solved. So a big M value is fine. If making it bigger changes the solution, then it was not big enough to start with.