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)? 
 A: 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$$
A: 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.
