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:

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

This is illustrated in Figure 5.

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.

Sun Jun 14 12:49:07 EDT 1998