INTEGER PROGRAMMING:CONCLUSIONS

CONCLUSIONS

IP problems arise frequently because some or all of the decision variables must be restricted to integer values. There also are many applications involving yes-or-no decisions (including combinatorial relationships expressible in terms of such decisions) that can be represented by binary (0–1) variables. These factors have made integer programming one of the most widely used OR techniques.

IP problems are more difficult than they would be without the integer restriction, so the algorithms available for integer programming are generally considerably less efficient than the simplex method. However, there has been tremendous progress over the past two or three decades in the ability to solve some (but not all) huge IP problems with tens or even hundreds of thousands of integer variables. This progress is due to a combination of three factors—dramatic improvements in IP algorithms, striking improvement in the linear programming algorithms used within IP algorithms, and the great speedup in com- puters. However, IP algorithms also will occasionally still fail to solve rather small problems (even as few as a hundred integer variables). Various characteristics of an IP problem in addition to its size, have a great influence on how readily it can be solved.

Nevertheless, size is one key factor in determining the time required to solve an IP problem, if it can be solved at all. The most important determinants of computation time for an IP algorithm are the number of integer variables and whether the problem has some special structure that can be exploited. For a fixed number of integer variables, BIP prob- lems generally are much easier to solve than problems with general integer variables, but adding continuous variables (MIP) may not increase computation time substantially. For special types of BIP problems containing a special structure that can be exploited by a special-purpose algorithm, it may be possible to solve very large problems (thousands of binary variables) routinely.

Computer codes for IP algorithms now are commonly available in mathematical programming software packages. Traditionally, these algorithms usually have been based on the branch-and-bound technique and variations thereof.

More modern IP algorithms now use the branch-and-cut approach. This algorithmic approach involves combining automatic problem preprocessing, the generation of cut- ting planes, and clever branch-and-bound techniques. Research in this area is continuing, along with the development of sophisticated new software packages that incorporate these techniques.

The latest development in IP methodology is to begin incorporating constraint programming. It appears that this approach will greatly expand our ability to formulate and solve IP models.

In recent years, there has been considerable investigation into the development of algorithms (including heuristic algorithms) for integer nonlinear programming, and this area continues to be an active area of research. (Selected Reference 7 describes some of the progress in this area.)