Operation Research course

TH E 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 b r an c h- and-cu t approach to sol...

A BRANCH-AND-BOUND ALGORITHM FOR MIXED INTEGER PROGRAMMING We shall now consider the general MIP problem, where some of the variables (say, I of them) are restricted to integer values (but not necessarily just 0 and 1) but the rest are ordinary continuous variables. For notational convenience, we shall order the variables so that the first I variables are the int e g e r - r estricte d variables. Therefore, the general form of the problem being considered is (When I = n , this problem becomes the pure IP problem.) We shall describe a basic branch-and-bound algorithm for solving this problem that, with a variety of refinements, has provided a standard approach to MIP. The structure of this algorithm was first developed by R. J. Dakin,9 based on a pioneering branch-and-bound algorithm by A. H. Land and A. G. Doig.10 This algorithm is quite similar in structure to the BIP algorithm presented in the pre- ceding section. Solving LP relaxations again provides the basis for both the...

THE BRANCH-AND-BOUND TECHNIQUE AND ITS APPLICATION TO BINARY INTEGER PROGRAMMING Because any bounded pure IP problem has only a finite number of feasible solutions, it is natural to consider using some kind of enumeration procedure for finding an optimal solution. Unfortunately, as we discussed in the preceding section, this finite number can be, and usually is, very large. Therefore, it is imperative that any enumeration procedure be cleverly structured so that only a tiny fraction of the feasible solutions actually need be examined. For example, dynamic programming (see Chap. 11) provides one such kind of procedure for many problems having a finite number of feasible solutions (although it is not particularly efficient for most IP problems). Another such approach is provided by the branch-and-bound technique. This technique and variations of it have been applied with some success to a variety of OR problems, but it is especially well known for its application to IP problems. Th...

SOME PERSPECTIVES ON SOLVING INTEGER PROGRAMMING PROBLEMS It may seem that IP problems should be relatively easy to solve. After all, linea r programming problems can be solved extremely efficiently, and the only difference is that IP problems have far fewer solutions to be considered. In fact, pu r e IP problems with a bounded feasible region are guaranteed to have just a f init e number of feasible solutions. Unfortunately, there are two fallacies in this line of reasoning. One is that having a fi- nite number of feasible solutions ensures that the problem is readily solvable. Finite num- bers can be astronomically large. For example, consider the simple case of BIP problems. With n variables, there are 2 n solutions to be considered (where some of these solutions can subsequently be discarded because they violate the functional constraints). Thus, each time n is increased by 1, the number of solutions is doubled . This pattern is referred to as the exponentia l growth of the dif...

EXAMPLE 3 Covering All Characteristics SOUTHWESTERN AIRWAYS needs to assign its crews to cover all its upcoming flights. We will focus on the problem of assigning three crews based in San Francisco to the flights listed in the first column of Table 12.4. The other 12 columns show the 12 feasible sequences of flights for a crew. (The numbers in each column indicate the order of the flights.) Exactly three of the sequences need to be chosen (one per crew) in such a way that every flight is covered. (It is permissible to have more than one crew on a flight, where the extra crews would fly as passengers, but union contracts require that the extra crews would still need to be paid for their time as if they were working.) The cost of assigning a crew to a particular sequence of flights is given (in thousands of dollars) in the bottom row of the table. The ob- jective is to minimize the total cost of the three crew assignments that cover all the flights. Formulation with Binary Variables....

EXAMPLE 2 Violating Proportionality The SUPERSUDS CORPORATION is developing its marketing plans for next year’s new products. For three of these products, the decision has been made to purchase a total of five TV spots for commercials on national television networks. The problem we will fo- cus on is how to allocate the five spots to these three products, with a maximum of three spots (and a minimum of zero) for each product. Table 12.3 shows the estimated impact of allocating zero, one, two, or three spots to each product. This impact is measured in terms of the p r o f i t (in units of millions of dollars) from the additional sales that would result from the spots, considering also the cost of producing the commercial and purchasing the spots. The objective is to allocate five spots to the products so as to maximize the total profit. This small problem can be solved easily by dynamic programming (Chap. 11) or even by inspection. (The optimal solution is to allocate two spots to...

SOME FORMULATION EXAMPLES We now present a series of examples that illustrate a variety of formulation techniques with binary variables, including those discussed in the preceding sections. For the sake of clarity, these examples have been kept very small. ( A somewhat larger formulation example , with dozens of binary variables and constraints, is included in the Solved Examples section of the book’s website.) In actual applications, these formulations typically would be just a small part of a vastly larger model. EXAMPLE 1 Making Choices When the Decision Variables Are The Research and Development Division of the GOOD PRODUCTS COMPANY has de- veloped three possible new products. However, to avoid undue diversification of the com- pany’s product line, management has imposed the following restriction: Restrictio n 1: From the three possible new products, at most two should be chosen to be produced. Each of these products can be produced in either of two plants. For administrati...