## Solving Integer Programming Problems By Exhaustion

Suppose we have the integer programming problem below< br /> Maximise
$O=6x_1+3x_2+x_3+2x_4$
subject to the constraints
$x_1+x_2+x_3+x_4 \le 8$
(1)
$2x_1+x_2+3x_3 \le 12$
(2)
$5x_2+x_3+3x_4 \le 6$
(3)
$0 \le x_1 \le 1$
(4)
$0 \le x_2 \le 1$
(5)
$0 \le x_3 \le 4$
(6)
$0 \le x_4 \le 2$
(7)
When a problem is required to have integer solutions, there are a finite number of possible solutions, so it is possible to analyse every possible solution to find the maximum value of
$O$
.
 $x_1$ $x_2$ $x_3$ $x_4$ $O$ (1) (2) (3) 0 0 0 0 0 0 0 0 1 0 0 0 6 1 2 0 0 1 0 0 3 1 1 5 1 1 0 0 9 2 3 5 0 0 1 0 1 1 3 1 1 0 1 0 7 5 2 5 0 1 1 0 4 2 4 6 1 1 1 0 10 3 6 6 0 0 2 0 2 2 6 2 1 0 2 0 8 3 8 2 0 1 2 0 5 3 7 7 1 1 2 0 11 4 9 7 0 0 3 0 3 3 9 3 1 0 3 0 9 4 11 3 0 1 3 0 6 4 10 8 1 1 3 0 12 5 12 8 0 0 4 0 4 4 12 4 1 0 4 0 10 5 14 4 0 1 4 0 7 5 13 9 1 1 4 0 13 6 15 9 0 0 0 1 2 1 0 3 1 0 0 1 8 2 2 3 0 1 0 1 5 2 1 8 1 1 0 1 11 3 3 6 0 0 1 1 3 2 3 4 1 0 1 1 9 3 5 4 0 1 1 1 6 3 4 9 1 1 1 1 12 4 6 9 0 0 2 1 4 3 6 5 1 0 2 1 10 4 8 5 0 1 2 1 7 4 7 10 1 1 2 1 13 5 9 10 0 0 3 1 5 4 9 6 1 0 3 1 11 5 11 6 0 1 3 1 8 5 10 11 1 1 3 1 14 6 12 11 0 0 4 1 6 5 12 7 1 0 4 1 12 6 14 7 0 1 4 1 9 6 13 12 1 1 4 1 15 7 15 12 0 0 0 2 4 2 0 6 1 0 0 2 10 3 2 6 0 1 0 2 7 3 1 11 1 1 0 2 13 4 3 11 0 0 1 2 5 3 3 7 1 0 1 2 11 4 5 7 0 1 1 2 8 4 4 12 1 1 1 2 14 5 6 12 0 0 2 2 6 4 6 8 1 0 2 2 12 5 8 8 0 1 2 2 9 5 7 13 1 1 2 2 15 6 9 13 0 0 3 2 7 5 9 9 1 0 3 2 13 6 11 9 0 1 3 2 10 6 10 14 1 1 3 2 16 7 12 14 0 0 4 2 8 6 12 10 1 0 4 2 14 7 14 10 0 1 4 2 11 7 13 15 1 1 4 2 17 8 15 15
The solution that maximises
$O$
and satisfies all the constraints is
$x_1=1, \: x_2=0, \: x_3=3, \: x_3=1$
.