next up previous contents
Next: Relationship to Linear Programming Up: A Tutorial on Integer Previous: Traveling Salesperson Problem

Solving Integer Programs


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.

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