To demonstrate the MIP algorithm, consider the following
integer programming problem.
|
 |
| To solve this problem using the MIP algorithm, begin by
ignoring the integer restrictions. This is called the LP-relaxation. The
graph of the feasible region for the LP-relaxation is shown above. The
integer solutions within this region are shown as points on the graph.
These points are the only feasible solutions to the original integer linear
programming problem. |
| The next step in the MIP algorithm is to solve the LP-relaxation,
using the simplex method. Since this problem has only two variables it
can be done graphically. |