CHAPTER 9

INTEGER PROGRAMMING

Review Questions

9.1-1 In some applications, such as assigning people, machines, or vehicles, decision variables

will make sense only if they have integer values. 9.1-2 Integer programming has the additional restriction that some or all of the decision variables

must have integer values. 9.1-3 The divisibility assumption of linear programming is a basic assumption that allows the

decision variables to have any values, including fractional values, that satisfy the functional and nonnegativity constraints. 9.1-4 The LP relaxation of an integer programming problem is the linear programming problem

obtained by deleting from the current integer programming problem the constraints that require the decision variables to have integer values. 9.1-5 Rather than stopping at the last instant that the straight edge still passes through the feasible

region, we now stop at the last instant that the straight edge passes through an integer point that lies within the feasible region. 9.1-6 No, rounding cannot be relied on to find an optimal solution, or even a good feasible

integer solution. 9.1-7 Pure integer programming problems are those where all the decision variables must be

integers. Mixed integer programming problems only require some of the variables to have integer values. 9.1-8 Binary integer programming problems are those where all the decision variables restricted

to integer values are further restricted to be binary variables. 9.2-1 The decisions are 1) whether to build a factory in Los Angeles, 2) whether to build a

factory in San Francisco, 3) whether to build a warehouse in Los Angeles, and 4) whether to build a warehouse in San Francisco. 9.2-2 Binary decision variables are appropriate because there are only two alternatives, choose

yes or choose no. 9.2-3 The objective is to find the feasible combination of investments that maximizes the total

net present value. 9.2-4 The mutually exclusive alternatives are to build a warehouse in Los Angeles or build a

warehouse in San Francisco. The form of the resulting constraint is that the sum of these variables must be less than or equal to 1 (x3 + x4 ≤ 1). 9.2-5 The contingent decisions are the decisions to build a warehouse. The forms of these

constraints are x3 ≤ x1 and x4 ≤ x2.

9-1

9.2-6 The amount of capital being made available to these investments ($10 million) is a

managerial decision on which sensitivity analysis needs to be performed. 9.3-1 A value of 1 is assigned for choosing yes and a value of 0 is assigned for choosing no. 9.3-2 Yes-or-no decisions for capital budgeting with fixed investments are whether or not to

make a certain fixed investment. 9.3-3 Yes-or-no decisions for site selections are whether or not a certain site should be selected

for the location of a certain new facility. 9.3-4 When designing a production and distribution network, yes-or-no decisions like should a

certain plant remain open, should a certain site be selected for a new plant, should a certain distribution center remain open, should a certain site be selected for a new distribution center, and should a certain distribution center be assigned to serve a certain market area might arise. 9.3-5 Should a certain route be selected for one of the trucks.

9.3-6 It is estimated that China is saving about $6.4 billion over the 15 years.

9.3-7 The form of each yes-or-no decision is should a certain asset be sold in a certain time

period. 9.3-8 The airline industry uses BIP for fleet assignment problems and crew scheduling problems. 9.4-1 A binary decision variable is a binary variable that represents a yes-or-no decision. An

auxiliary binary variable is an additional binary variable that is introduced into the model, not to represent a yes-or-no decision, but simply to help formulate the model as a BIP problem. 9.4-2 The net profit is no longer directly proportional to the number of units produced so a linear

programming formulation is no longer valid. 9.4-3 An auxiliary binary variable can be introduced for a setup cost and can be defined as 1 if

the setup is performed to initiate the production of a certain product and 0 if the setup is not performed. 9.4-4 Mutually exclusive products exist when at most one product can be chosen for production

due to competition for the same customers. 9.4-5 An auxiliary binary variable can be defined as 1 if the product can be produced and 0 if the

product cannot be produced. 9.4-6 An either-or constraint arises because the products are to be produced at either Plant 3 or

Plant 4, not both. 9.4-7 An auxiliary binary variable can be defined as 1 if the first constraint must hold and 0 if the

second constraint must hold. 9.5-1 Restriction 1 is similar to the restriction imposed in Variation 2 except that it involves more

products and choices. 9.5-2 The constraint y1 + y2 + y3 ≤ 2 forces choosing at most two of the possible new products.

9-2

9.5-3 It is not possible to write a legitimate objective function because profit is not proportional

to the number of TV spots allocated to that product. 9.5-4 The groups of mutually exclusive alternative in Example 2 are x1 = 0, 1, 2, or 3, x2 = 0, 1, 2,

or 3, and x3 = 0,1,2, or 3. 9.5-5 The mathematical form of the constraint is x1 + x4 + x7 + x10 ≥ 1. This constraint says that

sequence 1, 4, 7, and 10 include a necessary flight and that one of the sequences must be chosen to ensure that a crew covers the flight.

Problems

9.1

a) Let T = the number of tow bars to produce

S = the number of stabilizer bars to produce Maximize Profit = $130T + $150S subject to 3.2T + 2.4S ≤ 16 hours 2T + 3S ≤ 15 hours and T ≥ 0, S ≥ 0 T, S are integers. b) Optimal solution: (T,S) = (0,5). Profit = $750.

c)

A123456789BC

DEFUnit ProfitMachine 1Machine 2Tow Bars$130Stabilizer Bars$150HoursUsed1215<=<=HoursAvailable1615Total Profit$750Hours Used Per Unit Produced3.22.423Tow Bars0Stabilizer Bars5Units Produced 9-3

9.2 a)

A12345678910111213BCDEFModel A(high speed)Unit Cost$6,000Model B(lower speed)$4,000TotalCapacity80,000>=Total6>=6CapacityNeeded75,000Total Cost$28,000CapacityCopies per Day20,00010,000Model A(high speed)2>=1Model B(lower speed)4Min NeededPurchase

b) Let A = the number of Model A (high-speed) copiers to buy B = the number of Model B (lower-speed) copiers to buy Minimize Cost = $6,000A + $4,000B subject to A + B ≥ 6 copiers A ≥ 1 copier 20,000A + 10,000B ≥ 75,000 copies/day and A ≥ 0, B ≥ 0 A, B are integers. c) Optimal solution: (A,B) = (2,4). Cost = $28,000.

9-4