next up previous contents
Next: General Cutting Planes Up: Solving Integer Programs Previous: Branch and Bound

Cutting Plane Techniques


There is an alternative to branch and bound called cutting planes which can also be used to solve integer programs. The fundamental idea behind cutting planes is to add constraints to a linear program until the optimal basic feasible solution takes on integer values. Of course, we have to be careful which constraints we add: we would not want to change the problem by adding the constraints. We will add a special type of constraint called a cut. A cut relative to a current fractional solution satisfies the following criteria:

  1. every feasible integer solution is feasible for the cut, and
  2. the current fractional solution is not feasible for the cut.

This is illustrated in Figure 5.

Figure 5: A cut

There are two ways to generate cuts. The first, called Gomory cuts, generates cuts from any linear programming tableau. This has the advantage of ``solving'' any problem but has the disadvantage that the method can be very slow. The second approach is to use the structure of the problem to generate very good cuts. The approach needs a problem-by-problem analysis, but can provide very efficient solution techniques.

Michael A. Trick
Sun Jun 14 12:49:07 EDT 1998