Baker K.R. Optimization Modeling with Spreadsheets

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

Once we build the model and designate particular variables as integer or binary,

the next step is to examine the options in the Integer group of the Engine tab on the task

pane. The key option is the Integer Tolerance option, which should normally be set to

zero. At some other setting, such as 0.05, Solver is guaranteed to ﬁnd a solution that is

no worse than 5 percent away from the optimum, as measured by the objective func-

tion. Clearly, we would prefer to ﬁnd the very best solution, and this calls for an Integer

Tolerance parameter of zero. However, in some large models, a tight Integer Tolerance

level may require the solution procedure to take a great deal of time. Therefore, we

sometimes keep the level at 0.05 while we are debugging a large model, and we

leave it at that level if we ﬁnd that solution times are prohibitively lo ng otherwise.

If Solver can locate a solution at the 0.05 level in a reasonable amount of time, we

can experiment further by lowering the parameter toward zero.

With the integer variables designated and the Integer Tolerance option set, Solver

produces an optimal solution, shown in Figure 6.4, with a total cost of $8790. On the

surface, at least, there is no intuitive reason why we would have anticipated this result

based on the solution to the linear program. It is not, for example, a rounded-off ver-

sion of the optimal solution. Thus, by using the integer programming capability in

Solver, Callum can meet its stafﬁng requirements with minimum salary cost.

As suggested by this example, integer programming models look just like linear

programming models, except for the fact that certain variables are constrained to be

integer valued. The differences occur within Solver, not in the spreadsheet model.

Moreover, ﬁnding a solution with Solver simply requires the user to take two

additional steps beyond the typical procedure for solving linear programs—that is,

designating integer variables and setting the Integer Tolerance parameter. When the

only role of integers in a model is to avoid fractional values in what otherwise

would be a normal linear program, then the formulation principles we covered in

Figure 6.4. Optimal integer solution to Example 6.1.

216 Chapter 6 Integer Programming: Binary Choice Models

Chapters 2 and 3, along with the int constraint, are likely to sufﬁce. That was the case

in Example 6.1.

In some cases, such as the call center model, all of the variables are constrained to

be integers. This type of model is sometimes called a pure integer program. In other

cases, certain variables may be integers, but others are allowed to be noninteger. A

model containing both kinds of variables is called a mixed integer program. Using

Solver, the only difference between these two cases is the set of variables designated

by the int constraint.

At the level of building models for use with Solver, integer programming may

seem to be a minor technical extension of what we can already do with linear program-

ming. However, as we explore the formulation of integer programs using binary vari-

ables in this chapter and the next, a very different picture emerges. The opportunity to

use binary variables provides access to a class of models that is actually very different

from linear programming.

The solution algorithm within Solver for handling integer programs is generically

known as a branch and bound procedure. At the end of this chapter, we take a look at

how such a procedure works.

6.2. THE CAPITAL BUDGETING PROBLEM

A binary variable, which takes on the values 0 or 1, can represent a yes/no decision—

that is, a decision that represents a choice between taking an action and not taking it.

We sometimes think in terms of discrete projects, where the decision to undertake the

project is represented by the value 1 and the decision to forego the project is

represented by the value 0. A classical example arises in conjunction with the capital

budgeting problem, as illustrated by the Newton Corporation.

EXAMPLE 6.2

The Newton Corporation

Division A of the Newton Corporation has been allocated $40 million for capital projects this

year. Managers in Division A have examined various possibilities and have proposed ﬁve pro-

jects for the capital budgeting committee to consider. The projects cover a variety of activities

and functional areas, and there is just one of each type. The projects are listed below.

P1 Renovate the production facility for greater efﬁciency.

P2 License a new technology for use in production.

P3 Expand advertising by naming a stadium.

P4 Purchase land and construct a new headquarters building.

P5 Introduce a new product to complement the current line.

Each project has an estimated net present value (NPV), and each requires a capital expenditure,

which must come out of the budget for capital projects. The following table summarizes the pos-

sibilities, as they have been provided to the committee, with all ﬁgures in millions of dollars.

6.2. The Capital Budgeting Problem

217

Project P1 P2 P3 P4 P5

NPV 2.0 3.6 3.2 1.6 2.8

Expenditure 12 24 20 8 16

The committee would like to maximize the total NPV from projects selected, subject to a $40-

million limit on capital expenditures. This $40-million constraint makes it impossible to under-

take all ﬁve projects; a subset of the ﬁve must be selected. B

The problem facing the Newton Corporation can be posed as an allocation

model with one constraint, as shown below with objective function and constraint

scaled to represent millions of dollars.

Maximize z = 2.0P1 +3.6P2 +3.2P3 +1.6P4 +2.8P5

subject to

12P1 +24P2 +20P3 +8P4 +16P5 ≤ 40

A spreadsheet model for this problem is shown in Figure 6.5. (A feasible, but

suboptimal set of choices is displayed.) If we treat the model as if it were a simple

linear program, we can specify the problem as follows.

Objective: G8 (maximize)

Variables: B5:F5

Constraints: G11 ≤ I11

In the discussion that follows, we elaborate on the development and interpretation of the

integer programming model as it is derived from the linear programming model. Our

purpose is to develop some intuition for binary variables in optimization models,

and we won’t elaborate in the same way for the other modes we introduce later.

Figure 6.5. Linear program for Example 6.2.

218 Chapter 6 Integer Programming: Binary Choice Models

The optimal NPV in the linear program for Example 6.2 appears to be $8 million,

as shown in Figure 6.6, but the solution would require the selection of project P4 ﬁve

times. However, none of the projects can be implemented more than once. In particu-

lar, it is not possible to buy the same parcel of land and build new headquarters ﬁve

times; obviously, that activity can be done only once.

To prevent any project from being implemented several times, we can require

each of the variables to be no greater than 1. If we optimize the model as a linear

program, imposing an upper bound of 1 on each of the variables, the maximum

NPV comes to just over $7 million, as shown in Figure 6.7, but the optimal mix of

projects is P1, P4, P5, and one-ﬁfth of P3. However, none of the projects can be

done in a fractional amount. In the case of P3, we cannot pay for a fraction of a stadium

name; the project is indivisible and must be either accepted or rejected in its entirety.

No part-way adoption of any of the projects is possible. Therefore, we must use binary

variables, as all-or-nothing variables, to represent choices.

Figure 6.6. Optimal solution to the linear program for Example 6.2.

Figure 6.7. Optimal solution to the linear program for Example 6.2 with ceilings of 1.

6.2. The Capital Budgeting Problem 219

Having seen why a purely linear programming approach is unsuitable for the

situation at the Newton Corporation, we add the constraint that each variable is

binary. The model speciﬁcation is as follows.

Objective: G8 (maximize)

Variables: B5:F5

Constraints: G11 ≤ I11

B5:F5 ¼ binary

The optimal solution achieves a NPV of $6.8 million, achieved by accepting

projects P1, P3, and P4, as shown in Figure 6.8. This ﬁgure represents the largest

value that can be achieved with the ﬁve candidate projects from the allocation of a

$40 million budget.

The capital budgeting model captures a well known allocation problem, in which

each candidate project is either included in the solution once or not at all. Finding sol-

utions can be difﬁcult because of the “lumpy” nature of the projects as they consume

resources in the budget constraint. Let’s take a closer look at the nature of our solution.

In a problem with one constraint on expenditures, the intuitive approach would be

to rank the projects by the ratio of value achieved to capital expenditure required, or in

this case, the ratio of NPV to capital expense. If we calculate those ratios, we obtain the

following numbers.

Project P4 P5 P1 P3 P2

NPV 1.6 2.8 2.0 3.2 3.6

Expense 8 16 12 20 24

Ratio 0.200 0.175 0.167 0.160 0.150

Figure 6.8. Optimal integer solution for Example 6.2.

220 Chapter 6 Integer Programming: Binary Choice Models

In the table, we have ordered the projects with the highest ratio on the left. Therefore,

using ratios to represent priorities, the intuitive rule would suggest adopting projects

P4, then P5, and then continuing in order until the budget is consumed. If we followed

that logic, we would adopt P4 and P5, but their expenditures of $36 million would

leave no room in the budget for other projects, and the total NPV would be

$4.4 million. However, by judiciously departing from the priority ordering, we can

reject P5 and instead adopt P1 and P3, thus achieving a full use of the capital

budget and a NPV of $6.8 million. The lumpiness of capital expenses means that

we can’t adopt fractional projects and follow our intuitive sense of priorities.

Instead, we have to account for the implications of each combination of expenditures

in terms of the budget remaining when we examine which combinations of projects

make sense. The number of combinations is large enough that it becomes tedious to

write down all the possibilities. In large problems, that tas k would be prohibitively

time consuming, yet an integer programming model can provide us with optimal sol-

utions readily.

The capital budgeting model illustrates decisions that are of the yes/no variety.

In fact, all variables in the capital budgeting model are of this type. In other integer

programming models, some of the variables might correspond to yes/no decisions

(and thus to binary variables), while other variables resemble the familiar types of

decisions that we have seen in other linear programming models.

6.3. SET COVERING

The covering model is one of the basic linear programming model types. As intro-

duced in Chapter 2, the model contains covering decisions corresponding to variables

that are assumed to be divisible. However, when the decisions are of the yes/no var-

iety, we have a binary-choice version of the covering model known as the set-covering

problem. To describe how this model m ight arise, consider the situation at the

Metropolis Police Department.

EXAMPLE 6.3

Metropolis Police Department

The police department in the city of Metropolis, has divided the city into 15 patrol sectors so

patrol cars can respond quickly to service calls. Until recently, the streets have been patrolled

overnight by 15 patrol cars, one in each sector. However, severe budget cuts have forced the

city to eliminate some patrols. The chief of police has mandated that each sector should be

covered by at least one unit located within the sector or in an adjacent sector.

The simpliﬁed map (Figure 6.9) depicts the 15 patrol sectors in the city. Any pair of sectors

that share a boundary are considered to be adjacent. (Sectors 4 and 5 are adjacent, but not Sectors

3 and 5.) In addition, Sectors 7 and 14 are not accessible from each other because their boundary

is the site of the Goose Pond Dam, while Sectors 9 and 13 are not mutually accessible due to the

terrain of Moose Mountain, which is located at their boundary.

Having analyzed the map, the chief wants to know what number of patrol units will be

required to provide service to the city’s 15 sectors. B

6.3. Set Covering

221

Although the map is the basic source of data for this problem, we can use it to

create an adjacency array for modeling purposes. This array is shown in Figure 6.10.

In the ﬁgure, the numbered rows and columns correspond to the various sectors. An

entry of 1 appears in row i and column j if sectors i and j are adjacent. (Each sector

is considered adjacent to itself.)

A model for minimizing the required number of patrols can be constructed around

the adjacency array by deﬁning binary variables as follows.

= 1 if a patrol is assigned to sector j

= 0 otherwise

Then the objective function—the total number of patrols—can be expressed as

the sum of the y

values. In the model of Figure 6.11, this sum is represented as the

SUMPRODUCT of the decision row and a row containing all 1s. To formulate con-

straints, suppose we focus on row i in the array, which corresponds to sector i. The

SUMPRODUCT of this row and the decisions yields the number of patrols that can

service county i. In the problem, we require coverage from at least one patrol for

every row. In words, our model takes the following form.

Minimize z = the number of patrols

subject to

Patrols servicing sector i ≥ 1, ( for all i = 1, 2, ...,15)

In algebraic terms, we can let a

represent the adjacency data in the array of

Figure 6.10. That is, a

¼ 1 if sectors i and j are adjacent and a

¼ 0 if not. Then

Figure 6.9. Sector map for Example 6.3.

222 Chapter 6 Integer Programming: Binary Choice Models

we can write

Minimize z =



subject to



≥ 1, ( for all sectors i = 1, 2, ...,15)

In the spreadsheet of Figure 6.11, we have positioned the constraint information

immediately to the right of the data array because the rows of the array give rise to con-

straints. We then specify the model as follows.

Objective: R7 (minimize)

Variables: C5:Q5

Constraints: R11:R25 ≥ T11:T25

C5:Q5 ¼ binary

Figure 6.11 shows the optimal solution, obtained with the linear solver and an Integer

Tolerance of 0, which calls for assigning patrols to Sectors 3, 7, and 10. By using an

integer programming model, the police department can provide service to Metropolis

while minimizing the number of patrols needed.

The generic set covering problem involves the selection of objects to meet given

coverage requirements, where selection is a matter of binary choice. Each column in

the constraints of the model (refer to Figure 6.11 as an example) corresponds to an

object and the coverage it provides. When the coverage is expressed with 0s and 1s

(the constraint coefﬁcients in a column), we can think of the 1s as deﬁning a coverage

123456789101112131415

1 11000000

110000

2 11100000

000000

3 01110001

000000

4 00111101

000000

5 00011110

000000

6 00011111

000000

7 00001111

000111

8 00110111

000100

9 11100001

100100

1010000000

111100

1110000000

111000

1200000000

111110

1300000011

101110

1400000010

001111

15000000100 0 0 0 0 1 1

Figure 6.10. Adjacency array for Example 6.3.

6.3. Set Covering 223

set (i.e., the set of rows in which 1s appear). Thus, the selection of objects is equivalent

to the selection of sets, and the problem is to choose the minimum number of sets

and still provide the required coverage. This interpretation gives rise to the name

set-covering problem.

6.4. SET PACKING

As we saw in the previous section, the covering model of linear programming leads to

an analog in binary-choice programming. In a similar fashion, the allocation model of

linear program leads to another analog. This model contains allocation constraints

rather than covering constraints; otherwise, it resembles the set-covering model. To

describe how this model might arise, consider the expansion problem faced by the

Happy Landings Motel Company.

EXAMPLE 6.4

Happy Landings Motels

The Happy Landings Motel has been a successful one-of-a-kind business in its original location.

Its new owner has decided to replicate the motel at several locations and form a small chain.

More expansion will follow if this ﬁrst phase is a success. The new owner has identiﬁed nine

Figure 6.11. Optimal solution for Example 6.3.

224 Chapter 6 Integer Programming: Binary Choice Models

potential locations where a motel might be located. However, some of these locations are within

30 miles of each other, and the owner prefers to separate motels in the chain by at least 30 miles

to avoid cannibalizing demand. The following information about location conﬂicts has been

obtained from a map.

Potential

site

Potential sites

within 30 miles

21,5,7

3 5,6,8,9

46,7

5 2,3,6,8

6 3,4,5,7

72,4,6

83,5

The new owner wants to build motels on as many sites as possible, while adhering to the 30-mile

requirement. B

Again, the raw data for this problem comes from a map, organized according

to the list given in Example 6.4. For modeling purposes, it’s convenient to convert this

information into a conﬂict array. This array is shown in Figure 6.12, as part of the ulti-

mate model. In the ﬁgure, the numbered rows and columns correspond to the various

Figure 6.12. Optimal solution for Example 6.4.

6.4. Set Packing 225