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\]
.