INTEGER PROGRAMMING:SOME FORMULATION EXAMPLES

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:

Restriction 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 administrative reasons, management has imposed a second restriction in this regard.

Restriction 2: Just one of the two plants should be chosen to be the sole producer of the new products.

The production cost per unit of each product would be essentially the same in the two plants. However, because of differences in their production facilities, the number of hours of pro- duction time needed per unit of each product might differ between the two plants. These data are given in Table 12.2, along with other relevant information, including marketing

estimates of the number of units of each product that could be sold per week if it is pro- duced. The objective is to choose the products, the plant, and the production rates of the chosen products so as to maximize total profit.

In some ways, this problem resembles a standard product mix problem such as the Wyndor Glass Co. example described in Sec. 3.1. In fact, if we changed the problem by dropping the two restrictions and by requiring each unit of a product to use the production hours given in Table 12.2 in both plants (so the two plants now perform dif- ferent operations needed by the products), it would become just such a problem. In par- ticular, if we let x1, x2, x3 be the production rates of the respective products, the model then becomes

This constraint does not fit into a linear or an integer programming format, so the key question is how to convert it to such a format so that a corresponding algorithm can be used to solve the overall model. If the decision variables were binary variables, then the constraint would be expressed in this format as x1 + x2 + x3 < 2. However, with con- tinuous decision variables, a more complicated approach involving the introduction of aux- iliary binary variables is needed.

must hold, where the choice of which constraint must hold corresponds to the choice of which plant will be used to produce the new products. We discussed in the preceding sec- tion how such an either-or constraint can be converted to a linear or an integer programming format, again with the help of an auxiliary binary variable.

Formulation with Auxiliary Binary Variables. To deal with requirement 1, we intro- duce three auxiliary binary variables ( y1, y2, y3) with the interpretation 1 if xj > 0 can hold (can produce product j)

This now is an MIP model, with three variables (the xj) not required to be integer and four binary variables, so an MIP algorithm can be used to solve the model. When this is done (after substituting a large numerical value for M),2 the optimal solution is y1 = 1,

2In practice, some care is taken to choose a value for M that definitely is large enough to avoid eliminating any feasible solutions, but as small as possible otherwise in order to avoid unduly enlarging the feasible region for the LP relaxation (described in the next section) and to avoid numerical instability. For this example, a careful examination of the constraints reveals that the minimum feasible value of M is M = 9.

produce, choose Plant 2 for the production, and choose the production rates of 5—units per week for product 1 and 9 nits per week for product 3. The resulting total profit is $54,500 per week.