INTEGER PROGRAMMING:SOME PERSPECTIVES ON SOLVING INTEGER PROGRAMMING PROBLEMS

SOME PERSPECTIVES ON SOLVING INTEGER PROGRAMMING PROBLEMS

It may seem that IP problems should be relatively easy to solve. After all, linear programming problems can be solved extremely efficiently, and the only difference is that IP problems have far fewer solutions to be considered. In fact, pure IP problems with a bounded feasible region are guaranteed to have just a finite 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 2n 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 exponential growth of the difficulty of the problem. With n = 10, there are more than 1,000 solutions (1,024); with n = 20, there are more than 1,000,000; with n = 30, there are more than 1 billion; and so forth. Therefore, even the fastest computers are incapable of performing exhaustive enumeration (checking each solution for feasibility and, if it is feasible, calculating the value of the objective value) for BIP problems with more than a few dozen variables, let alone for general IP problems with the same number of integer variables. Fortunately, by starting with the ideas described in subsequent sections, today’s best IP algorithms are vastly superior to exhaustive enumeration. The improvement over just the past two or three decades has been dramatic. BIP problems that would have required years of computing time to solve 25 years ago now can be solved in seconds with today’s best commercial software. This huge speedup is due to great progress in three areas—dramatic improvements in BIP algorithms (as well as other IP algorithms), striking improvements in linear programming algorithms that are heavily used within the integer pro- gramming algorithms, and the great speedup in computers (including desktop computers). As a result, vastly larger BIP problems now are sometimes being solved than would have been possible in past decades. The best algorithms today are capable of solving some pure BIP problems with over a hundred thousand variables. Nevertheless, because of exponential growth, even the best algorithms cannot be guaranteed to solve every relatively small problem (less than a few hundred binary variables). Depending on their characteristics, certain relatively small problems can be much more difficult to solve than some much larger ones.4 When dealing with general integer variables instead of binary variables, the size of the problems that can be solved tend to be substantially smaller. However, there are exceptions. The second fallacy is that removing some feasible solutions (the noninteger ones) from a linear programming problem will make it easier to solve. To the contrary, it is only because all these feasible solutions are there that the guarantee usually can be given (see Sec. 5.1) that there will be a corner-point feasible (CPF) solution [and so a cor- responding basic feasible (BF) solution] that is optimal for the overall problem. This guar-

antee is the key to the remarkable efficiency of the simplex method. As a result, linear programming problems generally are considerably easier to solve than IP problems.

Consequently, most successful algorithms for integer programming incorporate a linear programming algorithm, such as the simplex method (or dual simplex method), as much as they can by relating portions of the IP problem under consideration to the corresponding linear programming problem (i.e., the same problem except that the integer restriction is deleted). For any given IP problem, this corresponding linear programming 4For information about predicting the time required to solve a particular integer programming problem, see Ozaltin, O. Y., B. Hunsaker, and A. J. Schaefer: “Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs,” INFORMS Journal on Computing, 23(3): 392–403, Summer 2011.

An Application Vignette

As of 2013, Taco Bell Corporation has approximately 5,600 quick-service restaurants in the United States and about 250 more in 20 other countries. It serves over 2 bil- lion meals per year.

At each Taco Bell restaurant, the amount of business is highly variable throughout the day (and from day to day), with a heavy concentration during the normal meal times. Therefore, determining how many employees should be scheduled to perform what functions in the restaurant at any given time is a complex and vexing problem.

To attack this problem, Taco Bell management instructed an OR team (including several consultants) to develop a new labor-management system. The team concluded that the system needed three major components:

(1) a forecasting model for predicting customer transactions at any time, (2) a simulation model (such as those described in Chap. 20) to translate customer transactions to labor requirements, and (3) an integer programming model to schedule employees to satisfy labor requirements and minimize payroll.

The integer decision variables for this integer programming model for any restaurant are the number of employees assigned to each of the shifts that begin at various specified times. The lengths of these shifts also are decision variables (constrained to be between minimum and maximum permissible shift lengths), but continuous decision variables in this case, so the model is a mixed IP model. The main constraints specify that the number of employees working during each 15-minute time interval must be greater than or equal to the minimum number required during that interval (according to the forecasting model).

This MIP model is similar to the linear programming model for a personnel scheduling example that is presented in Sec. 3.4. However, the key difference is that the number of employees working shifts at Taco Bell restaurants is much smaller than for this example in Sec. 3.4 that involves over 100 employees, so it is necessary to restrict these decision variables to integer values for the Taco Bell model (whereas noninteger values in a solution for the example with over 100 employees can readily be rounded to integer values with little loss of accuracy).

The implementation of this MIP model along with the other components of the labor-management system has provided Taco Bell with documented savings of $13 million per year in labor costs.

Source: J. Hueter and W. Swart: “An Integrated Labor- Management System for Taco Bell,” Interfaces, 28(1): 75–91, Jan.–Feb. 1998. (A link to this article is provided on our website, www.mhhe.com/hillier.)

problem commonly is referred to as its LP relaxation. The algorithms presented in the next two sections illustrate how a sequence of LP relaxations for portions of an IP prob- lem can be used to solve the overall IP problem effectively.

There is one special situation where solving an IP problem is no more difficult than solving its LP relaxation once by the simplex method, namely, when the optimal solution to the latter problem turns out to satisfy the integer restriction of the IP problem. When this situation occurs, this solution must be optimal for the IP problem as well, because it is the best solution among all the feasible solutions for the LP relaxation, which includes all the feasible solutions for the IP problem. Therefore, it is common for an IP algorithm to begin by applying the simplex method to the LP relaxation to check whether this for- tuitous outcome has occurred.

Although it generally is quite fortuitous indeed for the optimal solution to the LP re- laxation to be integer as well, there actually exist several special types of IP problems for which this outcome is guaranteed. You already have seen the most prominent of these special types in Chaps. 9 and 10, namely, the minimum cost flow problem (with integer parameters) and its special cases (including the transportation problem, the assignment prob- lem, the shortest-path problem, and the maximum flow problem). This guarantee can be given for these types of problems because they possess a certain special structure (e.g., see Table 9.6) that ensures that every BF solution is integer, as stated in the integer solutions property given in Secs. 9.1 and 10.6. Consequently, these special types of IP problems can be treated as linear programming problems, because they can be solved completely by a streamlined version of the simplex method.

Although this much simplification is somewhat unusual, in practice IP problems frequently have some special structure that can be exploited to simplify the problem. (Examples 2 and 3 in the preceding section fit into this category, because of their mutually exclusive alternatives constraints or contingent decisions constraints or set-covering constraints.) Sometimes, very large versions of these problems can be solved success- fully. Special-purpose algorithms designed specifically to exploit certain kinds of special structures can be very useful in integer programming.

Thus, the three primary determinants of computational difficulty for an IP problem are (1) the number of integer variables, (2) whether these integer variables are binary variables or general integer variables, and (3) any special structure in the problem. This situation is in contrast to linear programming, where the number of (functional) constraints is much more important than the number of variables. In integer programming, the number of constraints is of some importance (especially if LP relaxations are being solved), but it is strictly secondary to the other three factors. In fact, there occasionally are cases where increasing the number of constraints decreases the computation time because the number of feasible solutions has been reduced. For MIP problems, it is the number of in- teger variables rather than the total number of variables that is important, because the continuous variables have almost no effect on the computational effort.

Because IP problems are, in general, much more difficult to solve than linear programming problems, sometimes it is tempting to use the approximate procedure of sim- ply applying the simplex method to the LP relaxation and then rounding the noninteger values to integers in the resulting solution. This approach may be adequate for some ap- plications, especially if the values of the variables are quite large so that rounding creates relatively little error. However, you should beware of two pitfalls involved in this approach.

One pitfall is that an optimal linear programming solution is not necessarily feasible after it is rounded. Often it is difficult to see in which way the rounding should be done to retain feasibility. It may even be necessary to change the value of some variables by one or more units after rounding. To illustrate, consider the following problem:

impossible to round the noninteger variable x1 to 1 or 2 (or any other integer) and retain feasibility. Feasibility can be retained only by also changing the integer value of x2. It is easy to imagine how such difficulties can be compounded when there are hundreds or thousands of constraints and variables.

Even if an optimal solution for the LP relaxation is rounded successfully, there re- mains another pitfall. There is no guarantee that this rounded solution will be the optimal

Because there are only two decision variables, this problem can be depicted graphically as shown in Fig. 12.3. Either the graph or the simplex method may be used to find that the optimal solution for the LP relaxation is x = 2, x = 9, with Z = 11. If a graphical solution were not available (which would be the case with more decision variables), then the variable with the noninteger value x = 9 would normally be rounded in the feasible direction to x2 = 1. The resulting integer solution is x1 = 2, x2 = 1, which yields Z = 7. Notice that this solution is far from the optimal solution (x1, x2) = (0, 2), where Z = 10.

Because of these two pitfalls, a better approach for dealing with IP problems that are too large to be solved exactly is to use one of the available heuristic algorithms. These algorithms are extremely efficient for large problems, but they are not guaranteed to find an optimal solution. However, they do tend to be considerably more effective than the rounding approach just discussed in finding very good feasible solutions.5

5For recent research on heuristic algorithms, see Bertsimas, D., D. A. Iancu, and D. Katz: “A New Local Search Algorithm for Binary Optimization,” INFORMS Journal on Computing, 25(2): 208–221, Spring 2013.

One of the particularly exciting developments in OR in recent years has been the rapid progress in developing very effective heuristic algorithms (commonly called metaheuristics) for various combinatorial problems such as IP problems. Three prominent types of meta- heuristics (tabu search, simulated annealing, and genetic algorithms) will be described in Chap. 14. These sophisticated metaheuristics can even be applied to integer nonlinear pro- gramming problems that have locally optimal solutions that may be far removed from a globally optimal solution. They also can be applied to various combinatorial optimization problems, which frequently can be represented in a model that has integer variables but also has some constraints that are more complicated than for an IP model. (We’ll discuss such applications further in Chap. 14.)

Returning to integer linear programming, for IP problems that are small enough to be solved to optimality, a considerable number of algorithms now are available. However, no IP algorithm possesses computational efficiency that is nearly comparable to the sim- plex method (except on special types of problems). Therefore, developing IP algorithms has continued to be an active area of research. Fortunately, some exciting algorithmic advances have been made and additional progress can be anticipated during the coming years. These advances are discussed further in Secs. 12.8 and 12.9.

The most popular traditional mode for IP algorithms is to use the branch-and-bound technique and related ideas to implicitly enumerate the feasible integer solutions, and we shall focus on this approach. The next section presents the branch-and-bound technique in a general context, and illustrates it with a basic branch-and-bound algorithm for BIP prob- lems. Section 12.7 presents another algorithm of the same type for general MIP problems.