Consider the manufacture of television sets. A linear programming model might give a production plan of 205.7 sets per week. In such a model, most people would have no trouble stating that production should be 205 sets per week (or even ``roughly 200 sets per week''). On the other hand, suppose we were buying warehouses to store finished goods, where a warehouse comes in a set size. Then a model that suggests we purchase 0.7 warehouse at some location and 0.6 somewhere else would be of little value. Warehouses come in integer quantities, and we would like our model to reflect that fact.
This integrality restriction may seem rather innocuous, but in reality it has far reaching effects. On one hand, modeling with integer variables has turned out to be useful far beyond restrictions to integral production quantities. With integer variables, one can model logical requirements, fixed costs, sequencing and scheduling requirements, and many other problem aspects. LINGO can easily change a linear programming problem into an integer program.
The downside of all this power, however, is that problems with as few as 40 variables can be beyond the abilities of even the most sophisticated computers. While these small problems are somewhat artificial, most real problems with more than 100 or so variables are not possible to solve unless they show specific exploitable structure. Despite the possibility (or even likelihood) of enormous computing times, there are methods that can be applied to solving integer programs. The LINDO solver in LINGO is based on a method called branch and bound but there are others. The purpose of this chapter is to show some interesting integer programming applications and to describe some of these solution techniques as well as possible pitfalls.
First we introduce some terminology. An integer programming problem in which all variables are required to be integer is called a pure integer programming problem. If some variables are restricted to be integer and some are not then the problem is a mixed integer programming problem. The case where the integer variables are restricted to be 0 or 1 comes up surprising often. Such problems are called pure (mixed) 0-1 programming problems or pure (mixed) binary integer programming problems.