3
$\begingroup$

Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} :\begin{cases}x_1\le9\\x_2\le7\\x_3\le5\\3x_1+6x_2+8x_3=80\\x_1,x_2,x_3\in\mathbb{N}\end{cases}$$ Is there any algebraic method to compute the solution (I can't use the simplex method)?

$\endgroup$
  • 1
    $\begingroup$ the problem was given to my son who's 11...so I can't explain this method to him. Any ideas? $\endgroup$ – user214188 Feb 9 '15 at 16:09
  • 3
    $\begingroup$ @A.E In general the simplex method won't solve integer programming problems, unless one is lucky enough to get an integer-valued optimal solution in the relaxation. $\endgroup$ – Casteels Feb 9 '15 at 16:14
  • $\begingroup$ I found the solution using a computer, but what I miss is a working method which can be understood by someone who doesn't know algorithms concerning with linear programming... $\endgroup$ – user214188 Feb 9 '15 at 16:18
  • 1
    $\begingroup$ You want $x_3$ to be as big as possible, and $x_1$ to be as small as possible. Use the greedy method to find $x_3, x_2,$ and $x_1$ satisfying the equations with these criteria (not necessarily integer). Now find the best integer solution. Think about the values of the variables mod 3. $\endgroup$ – Peter Shor Feb 9 '15 at 17:21
2
$\begingroup$

The problem is beyond the typical 11-year-old but if he is bright at math you should be able to explain how to solve it. Does he have simple algebra?

The first thing to notice is that $3x_1+6x_2$ is divisible by 3, so $80-8x_3$ must also be divisible by 3. The only two allowable $x_3$ that satisfy this are $1$ and $4$.

Say $x_3 = 1$. Then the problem becomes minimize $x1 + x_2 +1$ with $$ x_1 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 72 $$ The last line of that says $x_1 = 24 - 2x_2$. But $x_2$ is at most $7$, so this means $x_1 \geq 10$ which contradicts $x_1 \leq 9$. So the choice $x_3 = 1$ doesn't allow a solution to the constraints at all.

Thus our solution will have $x_3 = 4$. Then the problem becomes minimize $x1 + x_2 + 4$ with $$ x_1 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 48 $$ The last line of that says $x_1 = 16 - 2x_2$. Replace $x_1$ and the problem becomes to minimize $20-x_2$ subject to $$ 16 - 2x_2 \leq 9 \\ x_2 \leq 7 \\ 3x_1 + 6x_2 = 48 $$ The first of those equations says $$ 2x_2 \geq 7 $$ Now because $x_2$ appears in the objective with a minus sign, we want $x_2$ to be as large as possible, thus $x_2 = 7$ and $x_1 = 2$.

So the solution will be $$ x_1 = 2 \\ x_2 = 7 \\x_3 = 4 \\x_1+x_2+x_3 = 13$$

$\endgroup$
1
$\begingroup$

Yep, Peter Shor got the right approach. You also need to use divisibility concepts to reduce the amount of work. Start with $x_3=5$. This would mean that $3x_1+6x_2=40$. But this can't lead to a solution because the left-hand side is divisible by 3, but the right-hand side is not! So try $x_3=4$, which gives $3x_1+6x_2=48$, which is divisible by $3$. Now try the maximum value for $x_2$, which is 7 and that gives $x_1= 2$.

This may or may not be convincing enough as proof, depending how formally the greedy approach needs to justified. The intuition is that $x_3$ contributes the most to the equality constraint, $x_1$ the least, while their appearance in the objective function is equal, so one unit of $x_3$ "buys" 8/3 units of $x_1$ in the objective function.

But clearly, the only other choice for $x_3$ (divisibility-wise) is 1, and that can't be met by plugging even the maximum values in $x_1+2x_2=25$; the max you can get maxing both $x_1=5$ and $x_2=7$ is 19.

A similar greedy argument goes for maxing $x_2$ instead of $x_1$ (once $x_3 = 4$ is settled); One unit of $x_2$ buys two units of $x_1$ in the objective function. If instead of $x_1 = 2$, $x_2=7$ you satisfy $x_1+2x_2=16$ with $x_1=4, x_2=6$, the objective function increases (by 1).

Alternatively, this remainder optimization problem being in only two variables ($x_1$, $x_2$), you can solve it by graphing its polyhedron.

enter image description here


The fact that the greedy method can solve certain classes of I[L]Ps can be given quite a formal proof(s) of correctenss; see the paper by V.V. Shenmaier for example, although I don't dream to suggest that's going to be accessible to an 11-year old.

$\endgroup$

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.