Baker K.R. Optimization Modeling with Spreadsheets

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

motel sites. An entry of 1 appears in row i and column j if sites i and j are within 30

miles of each other.

A model for maximizing the number of nonconﬂicting motel sites can be con-

structed around the conﬂict array by deﬁning binary variables

= 1 if a motel is assigned to site j

= 0 otherwise

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

sum of the y

values. In the model of Figure 6.12, 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 site i. The

SUMPRODUCT of this row and the decisions yields the number of assigned sites

(possibly including site i itself) that conﬂict with site i. In the problem, we require

the number of conﬂicts to be at most 1, for any site. In words, our model takes the

following form.

Maximize z = the number of sites

subject to

Sites in conflict with i ≤ 1, ( for all i = 1, 2, ...,9)

In algebraic terms, we can let a

represent the conﬂict data in the array of

Figure 6.12. That is, a

¼ 1 if sites i and j are within 30 miles and a

¼ 0 if not.

Then we can write

Maximize z =



subject to



≤ 1, ( for all sites i = 1, 2, ...,9)

In the spreadsheet of Figure 6.12, we specify the model as follows.

Objective: L7 (maximize)

Variables: C5:K5

Constraints: L10:L18 ≤ N10:N18

C5:K5 ¼ binary

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

Tolerance of 0, which calls for choosing sites 1, 4, and 8. By using an integer program-

ming model, the new owner can open as many new motels as the 30-mile limit allows.

The generic version of this problem involves the selection of objects that avoid

given conﬂict possibilities, with selection represented by binary choice. Each

column in the constraints of the model (refer to Figure 6.12 as an example) corre-

sponds to an object and the conﬂicts it generates. When the conﬂicts are expressed

with 0s and 1s (the constraint coefﬁcients in a column), we can think of the 1s as

226

Chapter 6 Integer Programming: Binary Choice Models

deﬁning a conﬂict 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 “pack in” the maxi-

mum number of sets without creating conﬂicts. This interpretation gives rise to the

name set-packing problem.

6.5. SET PARTITIONING

As another example of a binary choice model, we consider a matching problem. The

term “matching” refers to identifying pairs—that is, associating one object in a popu-

lation with exactly one other object. This structure differs from the assignment pro-

blem of Chapter 3, which calls for matching an object in one population, such as

products, to an object in another population, such as factories. Consider the exam-

scheduling problem as it arises at Oxbridge College.

EXAMPLE 6.5

Oxbridge College

Oxbridge College faces the problem of devising an exam schedule at the end of every term. By

tradition, the exam period lasts four days, and exams are scheduled in the morning of each day.

In other words, there are four available exam periods. To create an exam schedule, the college

registrar assigns courses to exam days according to the course meeting time. Thus, all courses

that meet Monday at 9am are assigned the same exam day. Eight distinct meeting times occur

in the college calendar, and the registrar wants to assign two to each of the four exam days.

However, when two times are assigned to the same exam day, some students may have a

time conﬂict because they are enrolled in courses that meet at those two times. Special arrange-

ments must then be made for such students. The registrar’s ofﬁce has an information system that

can determine, for any pair of class times, how many students are taking courses at both times.

With this information, the registrar would like to devise an exam schedule that makes the

number of exam conﬂicts as small as possible because that minimizes the number of cases in

which special arrangements have to be made. For the current term, the conﬂict numbers are

displayed in the following table.

Time T2 T3 T4 T5 T6 T7 T8

T1 20 15 18 14 16 11 8

T2 26 32 29 19 14 18

T3 40 32 29 26 20

T4 35 31 23 26

T5 31 26 27

T6 27 31

T7 26

It’s not necessary to ﬁll in the entire array because of symmetry: the number

of conﬂicts between Ti and Tj is the same as the number of conﬂicts between Tj and Ti.

6.5. Set Partitioning 227

Although it is convenient to present the data in a half-array, it can also be presented in a

horizontal layout, as in the standard linear programming format. (See rows 3 and 4 of

Figure 6.13.)

The essential decision in this problem is a binary choice for matching. The binary

decision variables x

are deﬁned as follows.

= 1 if class time Ti and class time Tj are assigned to the same exam day.

= 0 otherwise

Because symmetry allows us to work with just half the conﬂict array, we need to deﬁne

the x

variables only for i , j, which comes to 28 pairs. Then we can write the objec-

tive function as a SUMPRODUCT in the form



,wherec

represents the number

of conﬂicts occurring when Ti and Tj are assigned to the same exam day, and where

the sum is taken over all 28 potential assignments. Because the quantity c

contributes

to this sum only when x

¼ 1, the objective function measures the total number of con-

ﬂicts in the exam schedule. Constraints are needed to make sure that each class time is

assigned exactly one match. The algebraic model takes the following form.

Minimize z = 20x

+ 15x

+ 18x

+ ··· +26x

subject to

+ x

= 1

+ x

= 1

+ x

= 1

+ x

= 1

+ x

= 1

+ x

= 1

+ x

= 1

+ x

= 1

Figure 6.13. Spreadsheet model for Example 6.5.

228 Chapter 6 Integer Programming: Binary Choice Models

Figure 6.13 shows the spreadsheet model. The layout follows the standard linear

programming layout introduced in Chapter 2. By transforming the layout of the con-

ﬂict data from the original half-array into one long row in Figure 6.13, we facilitate the

standard layout.

The model speciﬁcation is the following.

Objective: A10 (minimize)

Variables: B7:AC7

Constraints: AD13:AD20 ¼ 1

B7:AC7 ¼ binary

After entering this information, we set Integer Tolerance to 0 and run the linear solver.

The minimal number of conﬂicts is 76, as shown in the ﬁgure, and the optimal pairings

are Time 1 with Time 5, Time 2 with Time 6, Time 3 with Time 8, and Time 4 with

Time 7. By using an integer programming model, Oxbridge can thus limit the number

of exam conﬂicts to the minimum possible level.

The binary-choice model in Figure 6.13 resembles the set covering model and the

set packing model, except for the constraint type. Again, we can think of columns as

sets, and in this case, the 1s in each column identify the pair of objects in the corre-

sponding match. The problem involves choosing a full match—that is, a collection

of pairs such that each object appears exactly once in the collection. The “exactly

once” requirement means that the sets selected must partition the population of objects

into mutually exclusive and exhaustive subsets. For that reason, this problem type is

often called a set-partitioning problem.

In Example 6.5, the number of class times is exactly equal to twice the number of

exam days. More generally, the number of class times could be slightly less than twice

the number of exam days, and a similar model could be used. For example, if there

were six class times rather than eight, then only two pairings would be needed, and

two of the class times would be unpaired. To accommodate this condition, we

could state the model constraints as LT inequalities and add a constraint to ensure

that at least two pairings took place.

Although Example 6.5 occurs in the setting of scheduling exams, the same kind

of matching model can be used to schedule class meetings (or training courses, or

conference sessions, etc.) when there are at most two items per time period. Several

additional conditions may apply as well, but the basic structure of such problems

often corresponds to the matching problem.

6.6. PLAYOFF SCHEDULING

An application area for integer programming that has received increasing attention

lately is the scheduling of sports teams in professional leagues. Although basic guide-

lines exist for the creation of a “balanced” schedule, a good deal of ﬂexibility remains,

and several speciﬁc considerations come into play in determining an “optimal” sche-

dule. As an example, a relatively new league in Latin America has just begun to exam-

ine the possibility of optimized scheduling.

6.6. Playoff Scheduling 229

EXAMPLE 6.6

The Latin American Soccer Association

Soccer is a popular spectator sport in Latin America, and as the year draws to a close, attention is

focused on the Latin American Soccer Association (LASA), which administers the annual

league competition. LASA also pays attention to trends in attendance, income from television

contracts, and the interactions between soccer games and the broader national culture. One of its

activities is drawing up a schedule for the season-ending playoff series.

The LASA league consists of 12 teams which compete against each other during a 24-week

regular season. Then, after a one-week break, the playoffs begin. Six teams—three from each

division—qualify for the playoffs based on their regular season performance. In the playoffs,

each team must play each of the other qualifying teams. After those games have been played,

the teams with the best record in each division meet in the championship game.

The playoff games are played on Saturdays, and each team plays every week. Several sche-

dules can be constructed that allow the playoffs to be completed in ﬁve weeks, but the LASA

Executive Board has determined that some schedules are preferable to others. In particular,

they have noticed that attendance is relatively greater when two teams of the same division

play each other (reﬂecting intradivision rivalries) and when games are relatively later in the

schedule (reﬂecting the importance of the later games in determining the ultimate division

winners). The Board has concluded that total attendance will be maximized if intra-division

games are played as late as possible in the schedule. B

When we examine the LASA problem closely, we can identify two basic

constraints: (1) each team must play every other team, and (2) each team plays exactly

one game each week. As a consequence, the schedule must require at least ﬁve weeks.

When we turn to the objective, we observe that each team plays two intradivision

rivals. Therefore, at best, the intradivision rivalries can be placed in the last two

weeks of the schedule. Normally, it is not too difﬁcult to devise a ﬁve-week schedule

containing the 15 required games, even with pencil and paper. However, it may not be

so easy to determine whether all intradivision rivalries can be placed in the last two (or

even three) weeks. That’s where an integer programming model can be useful.

To build the model, we rely on a binary-choice variable.

jkt

= 1 if teams j and k meet in week t of the schedule

0 otherwise

We need to deﬁne these x

jkt

variables for the 15 distinct pairs of teams corresponding

to j , k, as well as for each of the ﬁve weeks. This speciﬁcation gives us a total of

75 binary variables. Then it is straightforward to write the constraints of the problem.

For the one-game-per-week constraint, we write



k=j

jkt

= 1 for each team j and week t (6.1)

For the play-everyone-else constraint, we write



t=1

jkt

= 1 for each pair of teams ( j, k)(6.2)

230

Chapter 6 Integer Programming: Binary Choice Models

The model contains 30 constraints of type (6.1) and 15 constraints of type (6.2), for a

total of 45 constraints.

For the objective function, let’s assume we wish to maximize the following

expression.

Maximize z =



t=1



k=j

jkt

This expression represents a sum containing 75 terms. In selecting the coefﬁcients c

jkt

we ﬁrst need a mechanism that favors intradivision games over the other games. An

easy way is to associate a zero coefﬁcient with each pairing of teams from different

divisions. Then, for the intradivision games, we need a mechanism that favors later

weeks over earlier weeks. For this purpose, we could associate a positive objective

function coefﬁcient equal to the week number for each variable. Thus, we deﬁne

the following coefﬁcients

jkt

= t if intradivision teams j and k meet in week t of the schedule

0 otherwise

Perhaps the notion of “later week” deserves a closer look. In our assignment of coefﬁ-

cient values, we would permit the model to place two intradivision games in week 4

(making a contribution of 8 to the objective) rather than placing one intradivision game

in week 5 (making a contribution of just 5). However, if we do not ﬁnd that trade-off

desirable, we could use an alternative scheme.

The spreadsheet model for the LASA problem is not difﬁcult to build, but we

must keep its size in mind: 45 constraints and 75 variables. For reasons of readability,

Figure 6.14 shows just the upper left portion of the model. The variables appear in row

15, with rows 13 and 14 containing labels for the variables. Speciﬁcally, the pair ( j, k)

appears in row 13 and the week t appears in row 14. The ﬁrst set of constraints, corre-

sponding to (6.1) appears in rows 18–47, and the second set, corresponding to (6.2)

appears in rows 49–63. Row 48 reproduces the team pair in row 13 for easier

reference.

Figure 6.15 shows the entire model. All the constraints are equations with right-

hand-side constants equal to 1, so this model takes the form of a set-partitioning pro-

blem. The sets of constraints corresponding to (6.1) and (6.2) each have distinctive,

repeating clusters of nonzero coefﬁcients, which become visible when we zoom out

and display the entire model in one window. By examining the model at this zoom

level, we can scan the layout for possible typos or omissions.

The model speciﬁcation is the following

Objective: BZ16 (maximize)

Variables: C15:BY15

Constraints: BZ18:BZ47 ¼ 1

BZ49:BZ63 ¼ 1

C15:BY15 ¼ binary

6.6. Playoff Scheduling

231

A solution appears in both Figures 6.14 and 6.15, but the entire schedule is more use-

fully displayed in a table such as in Table 6.1, with shading to designate intradivision

games.

In the optimal schedule, all intradivision games are played in weeks 3 – 5.

Although six intradivision games must be played, they cannot all ﬁt into the ﬁnal

two weeks of the schedule.

The LASA scenario leads to a simple version of the playoff scheduling problem.

In actual practice, administrative bodies are concerned about several other features of

a schedule. For example, it’s common to keep track of home and away games and

to restrict a schedule so that no team plays more than two consecutive games at

home. In other settings, governing boards keep track of especially “strong” teams

and require that no team be scheduled to play two strong teams in successive

weeks. Finally, in many countries, soccer games compete with cultural events, so lea-

gues often prohibit games on dates corresponding to local festivals, bicycle races, or

Figure 6.14. Portion of the spreadsheet model for Example 6.6.

232 Chapter 6 Integer Programming: Binary Choice Models

Figure 6.15. Spreadsheet model for Example 6.6.

233

religious celebrations. Considerations such as these can be accommodated with integer

programming models, but sometimes the scheduling models grow quite large.

6.7. SOLVING A LARGE-SCALE SET PARTITIONING

PROBLEM

In this section, we examine a very large type of binary choice problem. It is considered

large because it contains a large number of variables, not to mention a large number of

feasible possibilities. Although the size of the problem outstrips the normal capabili-

ties of Solver, the set partitioning model provides us with an alternative approach to

ﬁnding a solution. The scenario at Courier Express gives rise to such a problem.

EXAMPLE 6.7

Courier Express

Courier Express serves 12 locations in its region with delivery service from a central transpor-

tation hub. Each day, trucks are sent out to several locations, where they deliver and collect

packages. Then the trucks return to the hub, where the pickups are sorted and sent on, and

where incoming packages are sorted and loaded on trucks in preparation for the next day’s

work. Each truck leaves the hub, visits some locations, and then returns to headquarters. The

dispatching problem is to route the trucks so that some truck visits each location. Distances

between locations are known. Courier Express wants to ﬁnd a dispatching plan that achieves

the minimum total distance traveled by its trucks each day. B

The distance data for Example 6.7 can be displayed in an array, as shown in

Figure 6.16. In this array, the element appearing in row i and column j is d

, the dis-

tance from location i to location j. Location 1 corresponds to the depot, and locations

2–13 correspond to the pickup and delivery points.

To analyze this problem, we ﬁrst assume that Courier Express deploys four trucks

and that each truck travels to three locations before returning to the depot. For each

truck, we want to assign a set of locations and a sequence for those locations. We

refer to this assignment as a segment. Each s egment has a total distance, dictated

by the sequence in which the truck visits the locations and returns to the depot. A

full solution is made up of four segments, one for each truck. For a group of four seg-

ments to be feasible, each location must be visited exactly once.

Table 6.1. Playoff Schedule for LASA

Week

12345

1 16 15 12 13 14

2 24 26 21 25 23

Team 3 35 34 36 31 32

4 42 43 45 46 41

5 53 51 54 52 56

6 61 62 63 64 65

234 Chapter 6 Integer Programming: Binary Choice Models

Figure 6.17 displays a model for this situation. Columns B–Z correspond to 25

segments. In column B, for example, the truck travels from the depot (city 1) to

cities 7, 12, and 9 in order, and then returns to the depot. This route is speciﬁed in

rows 25–29. Based on that route, the pairwise distances between locations are

recorded in rows 31 – 34 and their total appears in row 36. These 25 segments have

been selected randomly.

The remainder of Figure 6.17 shows a set partitioning model in which binary-

choice variables indicate whether a segment should be selected. The objective

function is the SUMPRODUCT of the binary variables and the total distances

in row 36. The constraints in the model require that each location must be selected

exactly once. Thus, the model attempts to ﬁnd the best feasible combination of

Figure 6.16. Distance data for Example 6.7.

Figure 6.17. Set partitioning model for Example 6.7.

6.7. Solving a Large-Scale Set Partitioning Problem 235