INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology.

Background

To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved.

Then came the next breakthrough in the mid-1980s, with the introduction of the branch- and-cut approach to solving BIP problems. There were early reports of very large problems with as many as a couple thousand variables being solved using this approach. This  created great excitement and led to intensive research and development activities to refine the approach that have continued ever since. At first, the approach was limited to pure BIP, but soon was extended to mixed BIP, and then to MIP problems with some general integer variables as well. We will limit our description of the approach to the pure BIP case.

It is fairly common now for the branch-and-cut approach to solve some problems with many thousand variables, and occasionally even hundreds of thousands of variables. As men- tioned in Sec. 12.4, this tremendous speedup is due to huge progress in three areas—dramatic improvements in BIP algorithms by incorporating and further developing the branch-and-cut approach, striking improvements in linear programming algorithms that are heavily used within the BIP algorithms, and the great speedup in computers (including desktop computers).

We do need to add one note of caution. This algorithmic approach cannot consistently solve all pure BIP problems with a few thousand variables, or even a few hundred vari- ables. The very large pure BIP problems solved have sparse A matrices; i.e., the percent- age of coefficients in the functional constraints that are nonzeros is quite small (perhaps less than 5 percent, or even less than 1 percent). In fact, the approach depends heavily upon this sparsity. (Fortunately, this kind of sparsity is typical in large practical problems.) Furthermore, there are other important factors besides sparsity and size that affect just how difficult a given IP problem will be to solve. IP formulations of fairly substantial size should still be approached with considerable caution.

Although it would be beyond the scope and level of this book to fully describe the algorithmic approach discussed above, we will now give a brief overview. Since this overview is limited to pure BIP, all variables introduced later in this section are binary variables.

The approach mainly uses a combination of three kinds12 of techniques: automatic

problem preprocessing, the generation of cutting planes, and clever branch-and-bound techniques. You already are familiar with branch-and-bound techniques, and we will not elaborate further on the more advanced versions incorporated here. An introduction to the other two kinds of techniques is given below.