Homework Help: Integer programming model (alternating constraints)

1. Nov 16, 2017

fishturtle1

1. The problem statement, all variables and given/known data
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$

2. Relevant equations

3. 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?

2. Nov 16, 2017

Ray Vickson

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.

Last edited: Nov 16, 2017
3. Nov 16, 2017

fishturtle1

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?

4. Nov 16, 2017

Ray Vickson

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.

5. Nov 16, 2017

fishturtle1

That makes sense, thank you.

6. Nov 16, 2017

FactChecker

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.