# Integer Linear Programming

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)?

• the problem was given to my son who's 11...so I can't explain this method to him. Any ideas? – user214188 Feb 9 '15 at 16:09
• @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. – Casteels Feb 9 '15 at 16:14
• 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... – user214188 Feb 9 '15 at 16:18
• 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. – Peter Shor Feb 9 '15 at 17:21

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$$

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.

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.