Ethan Frome - Brock University



Supplement to Chapter 9

Some Perspectives on Solving Binary

Integer Programming Problems

Have you been wondering how integer programming problems are solved? We now will touch briefly on this subject by focusing on binary integer programming (BIP) problems. Rest easy though. We will not delve into the technical details of any algorithms. Instead, our goal here is to give you an intuitive feeling for some of the difficulties and pitfalls involved with solving BIP problems.

To help ease you through this process, we will be referring a number of times to the following three examples of BIP models, where the symbol P represents the total profit that is to be maximized.

EXAMPLE 1:

Maximize [pic],

subject to

[pic]

and

[pic] are binary.

EXAMPLE 2:

Maximize [pic],

subject to

-x1 + x2 ≤ 0.5

x1 + x2 ≤ 1.5

and

[pic] are binary.

EXAMPLE 3:

Maximize [pic],

subject to

[pic]

[pic]

and

[pic] are binary.

These three examples are displayed graphically in Figures 1, 2, and 3, respectively, where the dots are the binary solutions, but only the dots in the shaded region are the feasible solutions.

[pic]

Figure 1 Graphical display of Example 1. The only feasible solutions are (0, 0), (1, 0), and

(0, 1), where (0, 1) is the optimal solution.

[pic]

Figure 2 Graphical display of Example 2. The only feasible solutions are (0, 0) and (1, 0), where (1, 0) is the optimal solution.

Figure 3 Graphical display of Example 3. The only feasible solutions are (0, 0), (1, 0), and

(0, 1), where (0, 1) is the optimal solution.

It may seem that BIP problems should be relatively easy to solve. After all, linear programming problems can be solved extremely efficiently, and the only difference is that BIP problems have far fewer solutions to be considered. Let us see.

Solving Very Small BIP Problems

As you can see in Figures 1, 2, and 3, each of the examples has just four solutions to be considered:

(0, 0), (1, 0), (0, 1) and (1, 1). In each case, one or two of these solutions then can be eliminated from further consideration because they are not feasible.

Thus, pure BIP problems with just two variables indeed are easy to solve. One way is the graphical method for integer programming presented in Section 9.1. This is essentially the graphical method for linear programming you learned in Chapter 2 except now, when pushing the objective function line in the direction of improving values of the objective function, you stop at the last instant when the objective function line passes through a feasible integer point. Figures 1, 2, and 3 illustrate this method where, in each case, the dashed line is the objective function line that passes through the optimal solution. Note that pushing this line further in the favorable direction does not lead to any more feasible binary solutions because we already had reached the optimal solution.

Perhaps an even easier way to solve small pure BIP problems such as these examples is the exhaustive enumeration method outlined below.

The Exhaustive Enumeration Method for Pure BIP

1. List all the binary solutions.

2. For each binary solution, check whether it is feasible by checking whether it satisfies all the functional constraints.

3. For each feasible solution, calculate the value of the objective function.

4. The feasible solution (or solutions) with the best value of the objective function is an optimal solution.

To illustrate the exhaustive enumeration method, we apply its four steps to Example 1 below. (See Figure 1 for visualization.)

1. The binary solutions for (x1, x2) are (0, 0), (1, 0), (0, 1), and (1, 1).

2. Example 1 has just one functional constraint, x1 + x2 [pic] 1. This constraint is satisfied by (0, 0),

(1, 0), and (0, 1), so these are feasible solutions. However, (1, 1) violates this constraint, so it is not a feasible solution.

3. For (0, 0), P = x1 + 2 x2 = 0 + 0 = 0.

For (1, 0), P = x1 + 2 x2 = 1 + 0 = 1.

For (0, 1), P = x1 + 2 x2 = 0 + 2 = 2.

4. Since the objective is to maximize P, the feasible solution with the best value of P is (0, 1). Therefore, the optimal solution is (x1, x2) = (0, 1).

The exhaustive enumeration method has one important advantage over the graphical method. Although the graphical method is limited to problems with just two variables, the exhaustive enumeration method still can be applied to larger problems. That is the good news. The bad news is that the exhaustive enumeration method quickly becomes unwieldy if the number of variables is increased very much.

For example, if the number of variables in a pure BIP problem is increased from 2 to 3, the number of binary solutions to be considered increases from 22 = 4 to 23 = 8. Increasing the number of variables from 3 to 4 then increases the number of binary solutions from 23 = 8 to 24 = 16. Thus, each time the number of variables 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.

The implications of this exponential growth become vivid with somewhat larger numbers of variables. With just 10 variables, we already are over a thousand binary solutions (or more precisely, 210 = 1,024). However, Table 1 indicates that this number continues to grow astronomically, with over a million binary solutions with 20 variables, over a billion binary solutions with 30 variables, etc. Therefore, even the fastest computers are incapable of performing the exhaustive enumeration method for pure BIP problems with more than a few dozen variables.

Table 1 Number of Binary Solutions That Need to Be Considered by the Exhaustive Enumeration Method for Pure BIP

| |Number of |Number of | |

| |Variables |Binary Solutions | |

| |10 |More than 1,000 | |

| |20 |More than 1,000,000 | |

| |30 |More than 1,000,000,000 | |

| |40 |More than 1,000,000,000,000 | |

| |50 |More than 1,000,000,000,000,000 | |

Solving Larger BIP Problems

Unfortunately, managers frequently must deal with pure BIP problems with more than a few dozen variables, sometimes many more. For this reason, extensive research has been conducted to develop sophisticated algorithms that can efficiently solve vastly larger problems than can the exhaustive enumeration method. Good progress has been made. In fact, recently developed algorithms have successfully solved certain huge BIP problems (into the thousands of variables). Nevertheless, because of exponential growth, even the best algorithms cannot be guaranteed to solve every relatively small problem (less than 100 binary variables). (However, even when an algorithm does not "solve" a problem in the sense of finding an optimal solution, the algorithm may still succeed in identifying a very good feasible solution that is acceptable to management.)

The best algorithms today fall into two categories, branch-and-bound algorithms and branch-and-cut algorithms. Some of these algorithms can solve mixed BIP problems, or even general integer programming problems (described in Section 9.1), as well as pure BIP problems. The Excel Solver uses a branch-and-bound algorithm that can solve any of these types of problems.

Although you should be aware of these two names for the best types of algorithms currently available, it is not important for a future manager to know much more about them.

However, one useful piece of information is that, even with the major recent improvements, the current algorithms for solving BIP problems still are not nearly as efficient as those for solving linear programming problems, including the simplex method. It has become routine for business firms to successfully solve linear programming problems with thousands of functional constraints and thousands of variables. This still is the exception rather than the rule for BIP problems.

Because of the remarkable efficiency of the simplex method, most successful algorithms for BIP incorporate the simplex method (or a variant) as much as they can by relating portions of the BIP problem under consideration to the corresponding linear programming problem. As discussed in Section 9.1, this corresponding linear programming problem commonly is referred to as its LP relaxation. For any BIP problem (pure or mixed), its LP relaxation is the identical problem except for replacing the constraint on each binary variable that

the variable is binary (i.e., it must be either 0 or 1)

by the constraint

0 [pic] the variable [pic] 1.

Thus, the new “relaxed” constraint still allows the value of either 0 or 1 but also allows any value in between. This new constraint really is a combination of a nonnegativity constraint on the variable and a functional constraint that imposes an upper bound of 1 on the variable. These are legitimate linear programming constraints, so the new “relaxed” problem is a valid linear programming problem that can be solved very quickly by the simplex method.

For Examples 1, 2, and 3, the linear programming models for their LP relaxations are given in the box in the upper right-hand corner of Figures 4, 5, and 6, respectively. Compare each model with the model for the example in the corresponding box in Figure 1, 2, and 3, respectively, and observe how the only difference is in the constraints in the last row. Then compare the graphical display of each example with the graph for its LP relaxation. Note how relaxing each example converts the set of feasible solutions from two or three dots to a complete feasible region for a linear programming problem that can be solved quickly by linear programming techniques. When the BIP problem has many variables rather than just two, its LP relaxation generally can be solved much more quickly than the BIP problem.

[pic]

Figure 4 Graphical display of the LP relaxation of Example 1. Note that its optimal solution is the same as the optimal solution for Example 1 shown in Figure 1.

[pic]

Figure 5 Graphical display of the LP relaxation of Example 2. Note that rounding its optimal solution (0.5, 1) to a binary solution, either (0, 1) or (1, 1), produces a solution that is not feasible for Example 2 shown in Figure 2.

[pic]

Figure 6 Graphical display of the LP relaxation of Example 3. Note that rounding its optimal solution (1, 0.9) to (1, 1) is not feasible for Example 3 shown in Figure 3. Rounding instead to the binary solution (1, 0) produces a solution that is feasible, but far from optimal, for Example 3.

For this reason, it is common for a BIP algorithm to begin by solving the LP relaxation. If all the variables that are required to be binary in the BIP problem turn out to be binary in the optimal solution for the LP relaxation, then this solution must also be optimal for the BIP problem, so nothing more needs to be done.

This is just what happens for Example 1. Figure 1 gives its optimal solution as (x1, x2) = (0, 1). Then Figure 4 shows that the optimal solution for the LP relaxation also is (x1, x2) = (0, 1).

Do you see why the fact that this optimal solution for the LP relaxation is binary guarantees that it also is optimal for Example 1? The reason is that the feasible region for the LP relaxation includes all the feasible solutions for the BIP problem, and both problems have the same objective function. Therefore, since (x1, x2) = (0, 1) is the best solution among all the feasible solutions for the LP relaxation of Example 1, and it is feasible for Example 1, it also must be the best feasible solution for Example 1.

Even when the optimal solution found for the LP relaxation is not all binary, this solution still is a good place to begin the search for an optimal solution for the BIP problem, so this is what BIP algorithms commonly do.

BIP problems arising in practice frequently have functional constraints with some special structure that can be exploited to simplify solving the problem. One example of constraints with special structure is provided by constraints for mutually exclusive alternatives. The functional constraint in Example 1,

[pic],

is of this type. As soon as one of these variables is set equal to 1, the other variable then automatically becomes 0 without any further consideration. This small simplification for solving Example 1 becomes much more pronounced when there are a substantial number of mutually exclusive alternatives.

For example, suppose that a BIP problem involves 30 yes-or-no decisions, where at most one of the first ten decisions can be yes (ten mutually exclusive alternatives), at most one of the second ten can be yes, and at most one of the third ten can be yes. These three sets of mutually exclusive alternatives would be represented by the constraints,

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 [pic] 1

x11 + x12 + x13 + x14 + x15 + x16 + x17 + x18 + x19 + x20 [pic] 1

x21 + x22 + x23 + x24 + x25 + x26 + x27 + x28 + x29 + x30 [pic] 1

Table 1 indicates that a BIP problem with this many binary variables has over a billion binary solutions. However, these three constraints reduce the number of feasible binary solutions to a vastly smaller number (a little over a thousand), which tremendously simplifies solving the problem.

This problem is said to have special structure because of the special form of these constraints that can greatly simplify solving the problem. Special-purpose algorithms designed specifically to simplify the solving by taking advantage of certain kinds of special structure (such as this one) are becoming increasingly important for efficiently solving real-world BIP problems.

The two primary determinants of computational difficulty for a BIP problem are (1) the number of binary variables and (2) 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. When solving BIP problems, the number of constraints is of some importance (especially if LP relaxations are being solved in the process), but it is strictly secondary to the other two 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 mixed BIP problems, it is the number of binary variables rather than the total number of variables that is important, because the continuous variables have almost no effect on the computational effort.

Pitfalls with Rounding an Optimal Solution for the LP Relaxation

Because BIP problems generally are much more difficult to solve than linear programming problems, sometimes it is tempting to use the following rounding procedure as an approximation. Simply apply the simplex method to the LP relaxation and then round the noninteger values to either 0 or 1 in the resulting solution. Recall that each binary variable in the BIP problem is only required to be between 0 and 1 (inclusively) in the LP relaxation. If such a variable still turns out to have a value of either 0 or 1 in the optimal solution obtained for the LP relaxation, the variable is fixed at that value. Thus, it is only when the variable has a value other than 0 or 1 in this solution that it is then rounded. The easiest way to round is to select whichever value, 0 or 1, is closer to the value obtained from the LP relaxation. (If the original value is 0.5, and so equally close to 0 and 1, we will break the tie by selecting 0.) This procedure is summarized below.

Rounding Procedure: Obtain an optimal solution for the LP relaxation. For each binary variable in the BIP problem, reset its value in this solution as follows.

If 0 [pic] the variable [pic] 0.5, reset the variable = 0.

If 0.5 < the variable [pic] 1, reset the variable = 1.

The resulting rounded solution hopefully will be at least nearly an optimal solution for the BIP problem, but beware that the two pitfalls discussed below may prevent this.

One major pitfall with the rounding procedure is that it may produce a solution that is infeasible for the BIP problem. To illustrate, consider Example 2 shown in Figure 2. The optimal solution for its LP relaxation is obtained in Figure 5 as (x1, x2) = (0.5, 1). Applying the rounding procedure,

since x1 = 0.5, reset x1 = 0;

since x2 = 1, keep x2 = 1.

However, Figure 5 shows that this rounded solution, (x1, x2) = (0, 1), is infeasible for the LP relaxation, and so for the BIP problem (Example 2) as well. Even if the tie for how to round x1 =0.5 is broken the other way by resetting x1 = 1 instead, the resulting rounded solution, (x1, x2) = (1, 1), also is infeasible. There is no way of rounding to obtain a feasible solution.

The story with Example 3 shown in Figure 3 is similar. Figure 6 indicates that the optimal solution for its LP relaxation is (x1, x2) = (1, 0.9). Using the rounding procedure,

since x1 = 1, keep x1 = 1;

since x2 = 0.9, reset x2 = 1.

Figures 6 and 3 demonstrate that this rounded solution, (x1, x2) = (1, 1), is infeasible for Example 3.

However, in this case, a different result is obtained if we round the noninteger variable, x2 = 0.9, the other way—all the way down to x2 = 0. The resulting rounded solution, (x1, x2) = (1, 0) is a feasible solution.

However, even if a way can be found of rounding the optimal solution for the LP relaxation to obtain a feasible solution for the BIP problem, there remains another pitfall. There is no guarantee that this feasible solution will be optimal, or even nearly optimal, for the BIP problem. In fact, it might even be a pretty poor solution.

Example 3 also illustrates this pitfall. As indicated by Figure 6, the only rounded solution that is feasible, (x1, x2) = (1, 0), gives an objective function value of P = 1. This is vastly inferior to the optimal solution, (x1, x2) = (0, 1), which yields P = 5.

Because of these pitfalls, we recommend against significant use of the rounding procedure for dealing with BIP problems. A better approach for dealing with BIP 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 procedure for finding very good feasible solutions.

REVIEW QUESTIONS

1. Describe the graphical method for integer programming when applied to pure BIP problems with two variables.

2. What is an advantage of the exhaustive enumeration method over the graphical method for solving pure BIP problems?

3. Why isn’t the exhaustive enumeration method a good way of solving pure BIP problems with a large number of variables?

4. For problems with more than a few variables, which is generally easier to solve, a BIP problem or a linear programming problem of the same size?

5. How does the LP relaxation of a BIP problem differ from the BIP problem?

6. Why is the LP relaxation relevant for helping to solve a BIP problem?

7. Give an example of a type of BIP problem that has special structure.

8. What are the two primary determinants of computational difficulty for a BIP problem?

9. What are two pitfalls with using the rounding procedure for BIP problems?

Glossary

Branch-and-bound algorithms: A type of algorithm for efficiently solving BIP problems.

Branch-and-cut algorithms: A type of algorithm for efficiently solving BIP problems.

Exhaustive enumeration method for pure BIP: A method for solving pure BIP problems by individually evaluating each binary solution.

Exponential growth: The difficulty of pure BIP problems is said to have exponential growth because the number of binary solutions doubles each time the number of variables increases by 1.

Graphical method for integer programming: A method first presented in Section 8.1 for solving integer programming problems (including BIP problems) that have only two decision variables by graphing the problem on a two-dimensional graph.

Heuristic algorithm: An algorithm that usually will find at least a good feasible solution, if not an optimal solution, extremely efficiently for large problems.

LP relaxation of a BIP problem: The linear programming problem obtained by replacing each constraint that a variable must be binary by the linear programming constraints that the variable must be nonnegative and must be less than or equal to 1.

Rounding procedure: An unreliable method for attempting to obtain an optimal solution, or at least a good feasible solution, for a BIP problem by rounding an optimal solution for its LP relaxation.

Special structure: Any special form in the functional constraints that makes the problem easier to solve.

Problems

1. Consider the following BIP model:

Maximize P =2 x1 +5x2 ,

subject to

10 x1 + 30x2 [pic] 30

95 x1 – 30x2 [pic] 75

and

x1,x2 are binary variables.

(a) Use the exhaustive enumeration method for pure BIP to solve this model.

(b) Use the graphical method for integer programming to solve this model.

(c) Use the rounding procedure. Does this yield a feasible solution? If so, calculate P and check whether this solution is optimal.

(d) Answer the questions in part (c) for each of the other solutions that can be obtained by rounding each noninteger value in the optimal solution for the LP relaxation either up or down.

2. Follow the instructions of Problem 1 for the following BIP model:

Maximize P = -5 x1 + 25x2,

subject to

-3 x1 + 30 x2 [pic] 27

3 x1 + x2 [pic] 4

and

x1,x2 are binary variables.

3. Reconsider the California Manufacturing Co. case study presented in Section 9.2. Referring to its BIP model given there, use the exhaustive enumeration method for pure BIP to find its optimal solution. Show your work. (You can check your answer by referring to the spreadsheet in Figure 9.4.)

4. Label each of the following statements as true or false, and then justify your answer by referring to specific statements (with page citations) in this supplement to Chapter 9.

(a) Linear programming problems are generally much easier to solve than BIP problems.

(b) For BIP problems, the number of integer variables is generally more important in determining the computational difficulty than is the number of functional constraints.

(c) To solve a BIP problem with an approximate procedure, one may apply the simplex method to the LP relaxation problem and then round each noninteger value to the nearest integer. The result will be a feasible but not necessarily optimal solution for the BIP problem.

-----------------------

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download