INTEGER PROGRAMMING:INNOVATIVE USES OF BINARY VARIABLES IN MODEL FORMULATION

INNOVATIVE USES OF BINARY VARIABLES IN MODEL FORMULATION

You have just seen a number of examples where the basic decisions of the problem are of the yes-or-no type, so that binary variables are introduced to represent these decisions. We now will look at some other ways in which binary variables can be very useful. In particular, we will see that these variables sometimes enable us to take a problem whose natural formulation is intractable and reformulate it as a pure or mixed IP problem.

This kind of situation arises when the original formulation of the problem fits either an IP or a linear programming format except for minor disparities involving combinator- ial relationships in the model. By expressing these combinatorial relationships in terms of questions that must be answered yes or no, auxiliary binary variables can be introduced to the model to represent these yes-or-no decisions. (Rather than being a decision vari- able for the original problem under consideration, an auxiliary binary variable is a binary variable that is introduced into the model of the problem simply to help formulate the model as a pure or mixed BIP model.) Introducing these variables reduces the problem to an MIP problem (or a pure IP problem if all the original variables also are required to have integer values).

Some cases that can be handled by this approach are discussed next, where the xj de- note the original variables of the problem (they may be either continuous or integer variables) and the yi denote the auxiliary binary variables that are introduced for the reformulation.

Either-Or Constraints

Consider the important case where a choice can be made between two constraints, so that only one (either one) must hold (whereas the other one can hold but is not required to do so). For example, there may be a choice as to which of two resources to use for a certain purpose, so that it is necessary for only one of the two resource availability con- straints to hold mathematically. To illustrate the approach to such situations, suppose that one of the requirements in the overall problem is that

i.e., at least one of these two inequalities must hold but not necessarily both. This re- quirement must be reformulated to fit it into the linear programming format where all

specified constraints must hold. Let M symbolize a very large positive number. Then this requirement can be rewritten as

The key is that adding M to the right-hand side of such constraints has the effect of eliminating them, because they would be satisfied automatically by any solutions that satisfy the other constraints of the problem. (This formulation assumes that the set of feasible solutions for the overall problem is a bounded set and that M is large enough that it will not eliminate any feasible solutions.) This formulation is equivalent to the set of constraints

Because the auxiliary variable y must be either 0 or 1, this formulation guarantees that one of the original constraints must hold while the other is, in effect, eliminated. This new set of constraints would then be appended to the other constraints in the overall model to give a pure or mixed IP problem (depending upon whether the xj are integer or continuous variables).

This approach is related directly to our earlier discussion about expressing combinatorial relationships in terms of questions that must be answered yes or no. The combinatorial relationship involved concerns the combination of the other constraints of the model with the first of the two alternative constraints and then with the second. Which of these two combinations of constraints is better (in terms of the value of the objective function that then can be achieved)? To rephrase this question in yes-or-no terms, we ask two complementary questions:

1. Should x1 + 4x2 < 16 be selected as the constraint that must hold?

2. Should 3x1 + 2x2 < 18 be selected as the constraint that must hold?

Because exactly one of these questions is to be answered affirmatively, we let the binary terms y and 1 - y, respectively, represent these yes-or-no decisions. Thus, y = 1 if the an- swer is yes to the first question (and no to the second), whereas 1 - y = 1 (that is, y = 0) if the answer is yes to the second question (and no to the first). Since y + 1 - y = 1 (one yes) automatically, there is no need to add another constraint to force these two decisions to be mutually exclusive. (If separate binary variables y1 and y2 had been used instead to represent these yes-or-no decisions, then an additional constraint y1 + y2 = 1 would have been needed to make them mutually exclusive.)

A formal presentation of this approach is given next for a more general case.

K out of N Constraints Must Hold

Consider the case where the overall model includes a set of N possible constraints such that only some K of these constraints must hold. (Assume that K < N.) Part of the optimization process is to choose the combination of K constraints that permits the objective function to reach its best possible value. The N - K constraints not chosen are, in effect, elimi- nated from the problem, although feasible solutions might coincidentally still satisfy some of them.

This case is a direct generalization of the preceding case, which had K = 1 and N = 2.

where M is an extremely large positive number. For each binary variable yi (i = 1, 2, . . . , N ), note that yi = 0 makes Myi = 0, which reduces the new constraint i to the original con- straint i. On the other hand, yi = 1 makes (di + Myi) so large that (again assuming a bounded feasible region) the new constraint i is automatically satisfied by any solution that satisfies the other new constraints, which has the effect of eliminating the original constraint i. There- fore, because the constraints on the yi guarantee that K of these variables will equal 0 and those remaining will equal 1, K of the original constraints will be unchanged and the other (N - K ) original constraints will, in effect, be eliminated. The choice of which K constraints should be retained is made by applying the appropriate algorithm to the overall problem so it finds an optimal solution for all the variables simultaneously.

Functions with N Possible Values

Consider the situation where a given function is required to take on any one of N given values. Denote this requirement by

so this new set of constraints would replace this requirement in the statement of the over- all problem. This set of constraints provides an equivalent formulation because exactly one yi must equal 1 and the others must equal 0, so exactly one di is being chosen as the value of the function. In this case, there are N yes-or-no questions being asked, namely, should di be the value chosen (i = 1, 2, . . . , N )? Because the yi respectively represent these yes- or-no decisions, the second constraint makes them mutually exclusive alternatives.

To illustrate how this case can arise, reconsider the Wyndor Glass Co. problem presented in Sec. 3.1. Eighteen hours of production time per week in Plant 3 currently is un- used and available for the two new products or for certain future products that will be ready for production soon. In order to leave any remaining capacity in usable blocks for these future products, management now wants to impose the restriction that the produc- tion time used by the two current new products be 6 or 12 or 18 hours per week. Thus, the third constraint of the original model (3x1 + 2x2 < 18) now becomes

The overall model for this new version of the problem then consists of the original model (see Sec. 3.1) plus this new set of constraints that replaces the original third constraint. This replacement yields a very tractable MIP formulation.

The Fixed-Charge Problem

It is quite common to incur a fixed charge or setup cost when undertaking an activity. For example, such a charge occurs when a production run to produce a batch of a par- ticular product is undertaken and the required production facilities must be set up to initiate the run. In such cases, the total cost of the activity is the sum of a variable cost related to the level of the activity and the setup cost required to initiate the activity. Fre- quently the variable cost will be at least roughly proportional to the level of the activity. If this is the case, the total cost of the activity (say, activity j) can be represented by a function of the form

where xj denotes the level of activity j (xj ::: 0), kj denotes the setup cost, and cj denotes the cost for each incremental unit. Were it not for the setup cost kj, this cost structure would suggest the possibility of a linear programming formulation to determine the optimal lev- els of the competing activities. Fortunately, even with the kj, MIP can still be used.

To formulate the overall model, suppose that there are n activities, each with the preceding cost structure (with kj ::: 0 in every case and kj > 0 for some j = 1, 2, . . . , n), and that the problem is to

subject to

given linear programming constraints.

To convert this problem to an MIP format, we begin by posing n questions that must be answered yes or no; namely, for each j = 1, 2, . . . , n, should activity j be undertaken (xj > 0)? Each of these yes-or-no decisions is then represented by an auxiliary binary vari- able yj, so that

will ensure that yj = 1 rather than 0 whenever xj > 0. The one difficulty remaining is that these constraints leave yj free to be either 0 or 1 when xj = 0. Fortunately, this difficulty is automatically resolved because of the nature of the objective function. The case where kj = 0 can be ignored because yj can then be deleted from the formulation. So we con- sider the only other case, namely, where kj > 0. When xj = 0, so that the constraints permit a choice between yj = 0 and yj = 1, yj = 0 must yield a smaller value of Z than yj = 1. Therefore, because the objective is to minimize Z, an algorithm yielding an optimal solution would always choose yj = 0 when xj = 0.

To summarize, the MIP formulation of the fixed-charge problem is

If the xj also had been restricted to be integer, then this would be a pure IP problem.

To illustrate this approach, look again at the Nori & Leets Co. air pollution problem described in Sec. 3.4. The first of the abatement methods considered—increasing the height of the smokestacks—actually would involve a substantial fixed charge to get ready for any increase in addition to a variable cost that would be roughly proportional to the amount of increase. After conversion to the equivalent annual costs used in the formulation, this fixed charge would be $2 million each for the blast furnaces and the open-hearth furnaces, whereas the variable costs are those identified in Table 3.14. Thus, in the preceding notation, k1 = 2, k2 = 2, c1 = 8, and c2 = 10, where the objective function is expressed in units of millions of dollars. Because the other abatement methods do not involve any fixed charges, kj = 0 for j = 3, 4, 5, 6. Consequently, the new MIP formulation of this problem is

Binary Representation of General Integer Variables

Suppose that you have a pure IP problem where most of the variables are binary variables, but the presence of a few general integer variables prevents you from solving the problem by one of the very efficient BIP algorithms now available. A nice way to circumvent this difficulty is to use the binary representation for each of these general inte- ger variables. Specifically, if the bounds on an integer variable x are

where the yi variables are (auxiliary) binary variables. Substituting this binary representation for each of the general integer variables (with a different set of auxiliary binary variables for each) thereby reduces the entire problem to a BIP model.

For example, suppose that an IP problem has just two general integer variables x1 and x2 along with many binary variables. Also suppose that the problem has nonnegativity constraints for both x1 and x2 and that the functional constraints include

Observe that each feasible value of x1 corresponds to one of the feasible values of the vector ( y0, y1, y2), and similarly for x2 and ( y3, y4, y5, y6). For example, x1 = 3 corre- sponds to ( y0, y1, y2) = (1, 1, 0), and x2 = 5 corresponds to ( y3, y4, y5, y6) = (1, 0, 1, 0).

For an IP problem where all the variables are (bounded) general integer variables, it is possible to use this same technique to reduce the problem to a BIP model. However, this is not advisable for most cases because of the explosion in the number of variables

involved. Applying a good IP algorithm to the original IP model generally should be more efficient than applying a good BIP algorithm to the much larger BIP model.1

In general terms, for all the formulation possibilities with auxiliary binary variables discussed in this section, we need to strike the same note of caution. This approach some- times requires adding a relatively large number of such variables, which can make the model computationally infeasible. (Section 12.5 will provide some perspective on the sizes of IP problems that can be solved.)