We have gone through a number of examples of integer programs. The
text gives a few others. A natural question is ``How can we get
solutions to these models?'' There are two common approaches.
Historically, the first method developed was based on cutting planes
(adding constraints to force integrality). In the last twenty years
or so, however, the most effective technique has been based on
dividing the problem into a number of smaller problems in a method
called *branch and bound*. Recently (the last ten years or so),
cutting planes have made a resurgence in the form of facets and
polyhedral characterizations. All these approaches involve solving a
series of *linear* programs. So that is where we will begin.

Sun Jun 14 12:49:07 EDT 1998