Baker K.R. Optimization Modeling with Spreadsheets

Подождите немного. Документ загружается.

the 25 segments. (It’s possible, however, that no feasible combination can be found.)

Although the initial set of decision variables shown in Figure 6.17 is infeasible, a

Solver run produces an optimal total distance of 791, as shown in Figure 6.18.

It is unlikely that the solution to the problem shown in Figure 6.18 is truly an

optimal solution to the overall problem because it is based on 25 randomly selected

segments. However, we can repeat the analysis by generating another set of ran-

domly selected segments and ﬁnding another solution. In fact, we can repeat this

procedure several times. Figure 6.19 provides a view of the entire model, starting

with the distance array in rows 3– 15. Rows 19–21 contain a segment generator,

which consists of random locations. These selections are determined by the formula

=RANDBETWEEN (2,13). We can generate a new set of segments by pressing the

F9 key; then we can copy the data in rows 19–21 and paste the values into rows

26–28. The formulas in the spreadsheet ﬁnd the individual distances between

locations by looking up values in the distance array, thus updating the objective func-

tion in cell AA38. The coefﬁcients on the left-hand side of the constraints are binary

values corresponding to the numbers in the segments of rows 26–28. Thus, as soon as

we paste data into rows 26–28, the formulas in the spreadsheet update the set partition-

ing model. A Solver run ﬁnds a new optimal solution.

The revised model gives rise to a solution that may be better or worse than the

previous one. However, we can repeat the segment generating procedure several

times, saving the best solution encountered. In one set of trials, we repeated the

procedure a dozen times and generated a solution with a total distance of 720.

How good is the solution thus obtained? It is difﬁcult to say for sure. However, the

repeated solut ion of a randomly generated subproblem seems to show considerable

potential for generating good solutions. In addition, we can strengthen our approach

in at least two ways. First, we can expand the model and include more segments.

Our 25-segment model gave rise to an integer programming model with 25 variables

and 12 constraints. It would not be difﬁcult to solve problems containing 40 or 50 seg-

ments, and the sampling mechanism would likely be more effective. (An experiment

using 40 segments with about a dozen trials generated a solution with a value of 627.)

Figure 6.18. Optimal solution for the model.

236 Chapter 6 Integer Programming: Binary Choice Models

Second, we don’t have to limit ourselves to segments containing exactly three loca-

tions. By constructing the model with some two-location segments and some four-

location segments, we increase our chances of ﬁnding an asymmetric combination

that might work even better. (Another experiment along these lines generated a sol-

ution value of 625.)

In this example, it is important to recognize that a direct attempt to ﬁnd an optimal

solution is likely to be impractical. If we tried to build a set-partitioning model contain-

ing all the possible segments, we would be facing the construction of a binary-choice

model with hundreds of millions of variables—well beyond the capabilities of Solver.

Perhaps we could imagine building a specialized algorithm tailored to the speciﬁc

problem we want to solve, but that approach has drawbacks, too. We would need

specialized code, and there would still be no guarantee that our algorithm would

converge in a reasonable amount of time. Relying on randomly-generated segments

may well be our best approach to ﬁnding at least a good solution.

6.8. THE ALGORITHM FOR SOLVING INTEGER

PROGRAMS

We can give a rough outline of the procedure that Solver uses to ﬁnd solutions to

integer programming models, drawing on an example. For this purpose, we revisit

Figure 6.19. Improved solution for Example 6.7.

6.8. The Algorithm for Solving Integer Programs 237

Example 2.1 (Brown Furniture Company), in which the problem is to determine the

best allocation of resources to the production of chairs, desks, and tables. Suppose

the problem has changed slightly so that there are 1900 available hours of fabrication

capacity, 1850 of machining, and 1450 of assembly, along with 9600 square feet of

wood. The linear programming problem is as follows.

Maximize z = 16C +20D +14T

subject to

4C +6D +2T ≤ 1900

3C +8D +6T ≤ 1850

9C +6D +4T ≤ 1450

30C +40D +25T ≤ 9600

Now we require all variables in the solution to be integers—that is, we want the

number of chairs, desks, and tables to all be integers so that we can interpret the sol-

ution literally, as a viable schedule for the month.

When Solver tackles an integer programming problem, its ﬁrst step is simply to

ignore the integer restrictions and treat the problem as a normal linear program.

This is called the relaxed problem, in the sense that the integer constraints are relaxed.

We refer to this linear program as problem P. If we are fortunate, the optimal solution

to this problem will contain integer decision variables and we will have solved the inte-

ger program. In this example, unfortunately, the optimal solution does not consist of

integers, and we obtain

Solution to P

C = 9.26, D = 227.8, T = 0

∗

= 4703.7

The value of the objective function is at least an upper bound on the best value we

could attain with integer values. No integer-valued solution could improve on the

solution to the relaxed problem, in which the integer constraints do not apply.

Solver recognizes that this solution is infeasible for the integer program and

creates two new linear programming problems to solve. The ﬁrst, which we refer

to as P

, corresponds to the original problem, with the additional constraint D ≤

227. The second, referred to as P

, corresponds to the original problem, with the

requirement D ≥ 228. In other words, we select a noninteger variable in the optimal

solution and append one of two constraints: we force this variable to be either

no larger than the next lower integer, or no smaller than the next higher integer.

We could use an arbitrary rule to select which variable to constrain or a rule with

a little more intelligence. Here, we choose the variable that is closest to an

integer value.

The better of the solutions to the integer versions of P

and P

must be the optimal

solution to the original problem. The reason is that together the two problems

correspond to all feasible choices of integer decision variables, because they

exclude only the cases associated with D-values strictly between 227 and 228, none

238

Chapter 6 Integer Programming: Binary Choice Models

of which is an integer. The implication is that we can forget the original problem for

now and concentrate just on the two modiﬁed problems that replaced it, P

and P

.If

we can solve both of those as integer programs, we will have the solution we seek.

Next, Solver tackles P

. Intuitively, we might expect the optimal solution to con-

tain D at a value of 227 because it “wants” to be 227.8, but the additional constraint

prevents it from being that large. Indeed, that is the case, and we obtain the following

result.

Solution to P

C = 9.33, D = 227, T = 1

∗

= 4703.3

As we might expect, the additional constraint leads to a drop in the optimal objective

function. More importantly, we still weren’t lucky enough to produce an integer sol-

ution because C remains noninteger.

When Solver tackles P

(where D ≥ 228), the optimal solution is as follows

Solution to P

C = 8.67, D = 228, T = 0

∗

= 4698.7

Having replaced the original problem with two modiﬁed problems, the status of

our search is shown in Figure 6.20. Here, each (linear programming) problem is rep-

resented by a node in the tree diagram. We say that we branch from the original pro-

blem P to the modiﬁed problems P

and P

. This means that we need only examine the

two replacement problems and not the original. In a sense, the search has been effec-

tive so far because we started with a model that generated two noninteger decision

variables, but now we are dealing with models that generate only one noninteger

decision variable.

Next, we select P

for branching. We recognize that the optimal solution is infeas-

ible for the integer version of P

because the value of C is noninteger. Hence, we create

two modiﬁed versions to solve, one in which we add the constraint C ≤ 9; the other in

which we add the constraint C ≥ 10. These bounds use the integers on either side of

the value of C in the optimal solution to P

. We refer to these problems as P

(with

Figure 6.20. First level of branching.

6.8. The Algorithm for Solving Integer Programs 239

C ≤ 9) and P

(with C ≥ 10). Now we can forget P

. The best among the solutions of

, P

, and P

will be the solution we seek.

When we solve P

we obtain the following result.

Solution to P

C = 9, D = 227, T = 1.17

∗

= 4700.3

The optimal solution is still noninteger, and the objective function has dropped

slightly from the value in P

. When we solve P

we obtain the following result

Solution to P

C = 10, D = 220, T = 10

∗

= 4700

Here, we have been fortunate, and the solution to the linear program contains

three integer-valued decision variables. It was not merely good fortune, of course:

The systematic choice of additional constraints helped lead us to an integer solution.

This solution is a feasible integer solution to the original problem. Now, the status

of our search is shown in Figure 6.21. In principle, we could pursue the search

from P

or P

Consider the linear program in P

and its objective function, which Solver has

optimized at 4698.7. The solution of P

is still not feasible for the integer program,

and the only way we can produce an integer-feasible solution is to impose additional

constraints. Thus, the value 4698.7 represents an upper bound on the best solution we

could ﬁnd in this part of the search tree. When we add constraints to P

, its objective

function cannot get better, so it can be no larger than 4698.7. Since we have already

found an integer-feasible solution with an objective function value of 4700, there is no

reason to look for a feasible solution to P

because its objective function value could

not be as good as the 4700 we have already found. We say that we have fathomed the

Figure 6.21. Second level of branching.

240 Chapter 6 Integer Programming: Binary Choice Models

search tree below P

, in the sense that we have implicitly evaluated all the branches that

might emanate from P

and determined from the bound that none of the branches

could be as good as the feasible solution we have already encountered.

We turn next to P

. Its bound is 4700.3. Because this value is larger than that of

the best integer solution we have found, it is still possible that we could ﬁnd a better

solution by branching from P

. Because the only noninteger decision variable in

is T ¼ 1.17, we branch to P

111

(adding the constraint T ≤ 1) and P

112

(adding the

constraint T ≥ 2), and we obtain the following results.

Solution to P

111

C = 9, D = 227, T = 1

∗

= 4698

Solution to P

112

C = 9, D = 226.4, T = 2

∗

= 4699.5

We now have enough information to identify the optimal solution to the original

problem. The sol ution to P

111

contains integer decision variables, but its objective

function is not as large as the integer-feasible solution to P

. In addition, we can

fathom P

112

because its upper bound is 4699.5, also not as large as the integer-feasible

solution to P

. The ﬁnal status of our search is shown in Figure 6.22, where we can see

that the solution to P

turns out to be optimal.

For any integer programming problem, Solver begins with the relaxed (linear)

problem and ﬁnds the optimal solution to the corresponding linear program. If

Figure 6.22. Final status of tree search.

6.8. The Algorithm for Solving Integer Programs 241

all of the variables are integer, the solution to the integer program has been found. If

not, x

will turn out to be either an integer or a fraction. If it is a fraction, Solver replaces

the original problem with two derived problems (P

and P

), each with an additional

constraint that forces the solution away from the fractional value in the original. On

the other hand, if x

is an integer, Solver then examines x

. Two alternatives may

arise, depending on whether x

is an integer or a fraction. If it is a fraction, Solver

creates two derived problems containing additional constraints that force the solution

away from the fractional value of x

. Otherwise, Solver proceeds to examine x

, and

so on.

At each stage in this procedure, Solver maintains a list of unsolved problems.

This list is structured so that the best integer-feasible solution to the problems on

the list will be the optimal solution for the original model. One at a time, problems

are removed from the list and addressed by solving them as linear programs. Either

the solution will be integer-feasible, or the problem will be replaced by two other

problems, each containing an additional constraint. This procedure requires the

solution of a series of linear programs. The list might get quite long, but the proce-

dure ultimately produces an optimal solution with integer-valued decision variables.

The replacement of a problem on the list by two others is called branching. This

name comes from a tree-like diagram that traces the different problems (as in

Figure 6.22).

As we saw, it is possible to curtail the list of problems that have to be solved. Any

time we encounter an integer-feasible solution, the branching in that portion of the tree

is ﬁnished. Elsewhere, branching may lead to an infeasible linear program, which also

terminates branching. Otherwise, we can try to use the bounds to fathom certain

problems and also terminate the branching. Suppose that, at some stage of solving a

maximization problem, the list contains a problem with a value (upper bound) that

is worse than the value of the objective function in an integer-feasible solution already

encountered. Whenever the bound on a derived problem is worse than the value of a

known integer solution, then the derived problem may be removed from the list

because its solution could never be optimal. (The mirror image of this statement

holds when we are minimizing: in that case, whenever the bound on a derived problem

is higher than the value of a known integer solution, then we can remove the derived

problem from the list.)

The generic name for the overall procedure Solver uses is branch and bound,

reﬂecting the two mechanisms that guide the search. Branching replaces a problem

on the list with two problems that are, in some sense, closer to being solved as integer

programs. Bounding explores whether a particular problem could just be deleted from

the list because it offers no hope of ﬁnding an optimum. Nevertheless, the essence of

the procedure is to solve a number of linear programs, to replace one problem with two

whenever an integer constraint is violated, and to use bounds to remove problems from

the list in order to reduce the workload. Because this procedure relies on the solution of

many linear programs, it is as reliable a procedure as the linear solver on which it

depends. That is, the branch and bound procedure is guaranteed to produce a global

optimum.

242

Chapter 6 Integer Programming: Binary Choice Models

SUMMARY

The ability to treat variables as integer valued, and in particular, the ability to designate variables

as binary, opens up a wide variety of optimization models that can be addressed with Solver.

This chapter introduced two broad classes of models that can be handled effectively with

Solver. The ﬁrst type of model is one that resembles a linear program but with the requirement

that certain variables must be integer valued. For the purposes of using Solver, this requirement

is added to the linear programming model as an additional constraint. The second type of model

is one in which certain decisions exhibit an all-or-nothing structure, representing actions that are

indivisible. Such decisions are modeled by binary variables, which are simply integer-valued

variables no less than zero and no greater than one. Binary variables allow us to model the occur-

rence of yes/no choices and to exploit Solver, provided that the structure of the model is linear in

all other respects.

In this second category, we explored three closely related model structures: set covering, set

packing, and set partitioning. In the basic form of these models, the objective function coefﬁ-

cients and the right-hand side constants are 1s, but generalizations are also possible, as illustrated

in some of the exercises at the end of this chapter.

In the next chapter, we examine a broader set of integer programming models, based on the

ability to represent logical constraints using binary variables. In those models, the logical con-

ditions do not seem linear, but they can be expressed in linear forms with the help of binary

variables.

EXERCISES

6.1. Callum Communications (Revisited) Revisit Example 6.1. Suppose that the objective

at Callum Communications is to minimize the number of employees, rather than to mini-

mize the total cost.

(a) What is the minimum number of employees needed at the call center?

(b) Does the solution in (a) achieve the minimum salary cost?

6.2. Make or Buy A sudden increase in the demand for smoke detectors has left Acme

Alarms with insufﬁcient capacity to meet demand. The company has seen monthly

demand from its retailers for its electronic and battery-operated detectors rise to 20,000

and 10,000, respectively, and Acme wishes to continue meeting demand. Acme’s

production process involves three departments: Fabrication, Assembly, and Shipping.

The relevant quantitative data on production and prices are summarized below.

Monthly hours Hours/unit Hours/unit

Department available (electronic) (battery)

Fabrication 2000 0.15 0.10

Assembly 4200 0.20 0.20

Shipping 2500 0.10 0.15

Variable cost/unit $18.80 $16.00

Retail price $29.50 $28.00

Exercises

243

The company also has the option to obtain additional units from a subcontractor,

who has offered to supply up to 20,000 units per month in any combination of electronic

and battery-operated models, at a charge of $21.50 per unit. For this price, the subcontrac-

tor will test and ship its models directly to the retailers without using Acme’s production

process.

(a) Acme wants an implementable schedule, so all quantities must be integers. What are

the maximum proﬁt and the corresponding make/buy levels?

(b) Compare the maximum proﬁt in (a) to the maximum proﬁt achievable without integer

constraints. Does the integer solution correspond to the rounded-off values of the

noninteger solution? By how much (in percentage terms) do the integer restrictions

alter the value of the optimal objective function?

6.3. Selecting an Investment Portfolio An investment manager wants to determine an opti-

mal portfolio for a wealthy client. The fund has $2.5 million to invest, and its objective is

to maximize total dollar return from both growth and dividends over the course of the

coming year. The client has researched eight high-tech companies and wants the portfolio

to consist of shares in these ﬁrms only. Three of the ﬁrms (S1 –S3) are primarily software

companies, three (H1 –H3) are primarily hardware companies, and two (C1 –C2) are

internet consulting companies. The client has stipulated that no more than 40 percent

of the investment be allocated to any one of these three sectors. To assure diversiﬁcation,

at least $100,000 must be invested in each of the eight stocks. Moreover, the number of

shares invested in any stock must be a multiple of 1000.

The table below gives estimates from the investment company’s database relating to

these stocks. These estimates include the price per share, the projected annual growth rate

in the share price, and the anticipated annual dividend payment per share.

Stock

S1 S2 S3 H1 H2 H3 C1 C2

Price per share $40 $50 $80 $60 $45 $60 $30 $25

Growth rate 0.05 0.10 0.03 0.04 0.07 0.15 0.22 0.25

Dividend $2.00 $1.50 $3.50 $3.00 $2.00 $1.00 $1.80 $0.00

(a) Determine the maximum return on the portfolio. What is the optimal number of

shares to buy for each of the stocks? What is the corresponding dollar amount

invested in each stock?

(b) Compare the solution in which there is no integer restriction on the number of shares

invested. By how much (in percentage terms) do the integer restrictions alter the

value of the optimal objective function? By how much (in percentage terms) do

they alter the optimal investment quantities?

6.4. Production Planning for Components Rummel Electronics produces two PC cards, a

modem and a network adapter. Demand for these two products exceeds the amount that

the ﬁrm can make, but there are no plans to increase production capacity in the short run.

Instead, the ﬁrm plans to use subcontracting.

The two main stages of production are fabrication and assembly, and either step can

be subcontracted for either type of card. However, the company policy is not to subcon-

tract both steps for either product. (That is, if modem cards are fabricated by a

244 Chapter 6 Integer Programming: Binary Choice Models

subcontractor, then they must be assembled in-house.) Components made by subcontrac-

tors must pass through the shipping and receiving departments, just like components

made internally. At present, the ﬁrm has 5200 hours available in fabrication, 3600 in

assembly and 3200 in shipping/inspection. The production requirements, in hours per

unit, are given in the following table.

Product/mode Fab. Ass. Ship.

Modem, made entirely in-house 0.35 0.16 0.08

Network, made entirely in-house 0.47 0.15 0.12

Modem, fabricated by subcontractor – 0.18 0.10

Network, fabricated by subcontractor – 0.16 0.15

Modem, assembled by subcontractor 0.35 – 0.09

Network, assembled by subcontractor 0.47 – 0.14

The direct material costs for the modem cards are $3.25 for manufacturing and $0.50

for assembly; for network cards, the costs are $6.10 and $0.50. Subcontracting the man-

ufacturing operation costs $5.35 for modem cards and $8.50 for network cards.

Subcontracting the assembly operation costs $1.50 for either product. Modem cards

sell for $20, and network cards sell for $28. The ﬁrm’s policy, for each product, is that

at most 40 percent of the units produced can have subcontracted fabrication, and at

most 70 percent of the units can have subcontracted assembly.

(a) Determine the production and subcontracting schedule that will maximize proﬁts,

given that Rummel Electronics wishes its schedule to contain an integer number of

units produced and subcontracted.

(b) Solve the problem without the integer restrictions. What is the solution? By how

much (in percentage terms) do the restrictions alter the value of the optimal objective

function?

6.5. Catering Logistics Jessica’s Catering Service bakes and delivers lasagnas to parties

and group meetings. In a typical week, Jessica has around 40 orders. Each order involves

a speciﬁc amount of the required lasagna in pounds. A small group would need about

20 lb, whereas a large group would need almost triple that amount. The following

table shows the different customer orders that have come in this week, grouped into

eight categories by weight.

Job type 12345678

Weight (lbs) 20 25 30 35 40 45 50 55

Number 10 5473921

Jessica has an inventory of 25 six-lb trays and 18 ten-lb trays. Although she appears to

have enough capacity in her trays, she would like to plan her orders so that the amount

of excess lasagna is kept to a minimum.

How many six-lb trays and ten-lb trays should Jessica use for each of the orders?

6.6. Location of Services The Division of Motor Wyoming (DMV) in Wyoming operates

several ofﬁces around the state. Citizens must travel to one of these ofﬁces to register a car,

Exercises

245