11 - Integer programming: theory and algorithms

Summary

Introduction

A linear programming model for constructing a portfolio of assets might produce a solution with 3205.7 shares of stock XYZ and similarly complicated figures for the other assets. Most portfolio managers would have no trouble rounding the value 3205.7 to 3205 shares or even 3200 shares. In this case, a linear programming model would be appropriate. Its optimal solution can be used effectively by the decision maker, with minor modifications. On the other hand, suppose that the problem is to find the best among many alternatives (for example, a traveling salesman wants to find a shortest route going through ten specified cities). A model that suggests taking fractions of the roads between the various cities would be of little value. A 0,1 decision has to be made (a road between a pair of cities is either on the shortest route or it is not), and we would like the model to reflect this.

This integrality restriction on the variables is the central aspect of integer programming. From a modeling standpoint, integer programming has turned out to be useful in a wide variety of applications. With integer variables, one can model logical requirements, fixed costs, and many other problem aspects. Many software products can change a linear programming problem into an integer program with a single command.

The downside of this power, however, is that problems with more than a thousand variables are often not possible to solve unless they show a specific exploitable structure.