Consider the following all-integer linear program:

Max 1 x1 + 1x2

s.t.

4x1 + 16x2 22

1x1 + 15x2 15

2x1 + 1x2 9

x1, x2 0 and integer

Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.

Solve the LP Relaxation of this problem.

The optimal solution to the LP Relaxation is shown on the above graph to be x1 = 4, x2 = 1. Its value is 5.

Find the optimal integer solution

The optimal integer solution is the same as the optimal solution to the LP Relaxation. This is always the case whenever all the variables take on integer values in the optimal solution to the LP Relaxation.