Problem Set

Problem

A young couple, Eve and Steven, want to divide their main household chores (marketing, cooking, dishwashing, and
laundering) between them so that each has two tasks but the total time they spend on household duties is kept to a
minimum.
Their efficiencies on these tasks differ, where the time each would need to perform the task is given by the
following table.

Formulate a Binary Integer Programming problem and solve.

Problem
Caliente City is located in a particularly warm and arid part of the United States, so it is especially prone to the
occurrence of fires. The city has become a popular place for senior citizens to move to after retirement, so it has been
growing rapidly and spreading well beyond its original borders.

However, the city still has only one fire station, located in the congested center of the original town site. The result
has been some long delays in fire trucks reaching fires in the outer parts of the city, causing much more damage than
would have occurred with a prompt response. The city’s residents are very unhappy about this, so the city council has
directed the city manager to develop a plan for locating multiple fire stations throughout the city (including perhaps
moving the current fire station) that would greatly reduce the response time to any fire. In particular, the city council
has adopted the following policy about the maximum acceptable response time for fire trucks to reach a fire
anywhere in the city after being notified about the fire.

Fire Station in Tract

1 2 3 4 5 6 7 8
1 2 8 18 9 23 22 16 28
Respons 2 9 3 10 12 16 14 21 25
e times 3 17 8 4 20 21 8 22 17
(minutes 4 10 13 19 2 18 21 6 12
) for a 5 21 12 16 13 5 11 9 12
fire in 6 25 15 7 21 15 3 14 8
tract 7 14 22 18 7 13 15 2 9
8 30 24 15 14 17 9 8 3
Cost of
350 250 450 300 50 400 300 200
Station($thousands)
Response time ≤ 10 minutes

Having had a management science course in college, the city manager recognizes that BIP provides her with a powerful
tool for analysing this problem. To get started, she divides the city into eight tracts and then gathers data on the
estimated response time for a fire in each tract from a potential fire station in each of the eight tracts. These data are
shown in the Table below. For example, if a decision were to be made to locate a fire station in tract 1 and if that fire
station were to be used to respond to a fire in any of the tracts, the second column of Table shows what the
(estimated) response time would be. (Since the response time would exceed 10 minutes for a fire in tracts 3, 5, 6, 7, or
8, a fire station actually would need to be located nearer to each of these tracts to satisfy the city council’s new policy.)
The bottom row of Table shows what the cost would be of acquiring the land and constructing a fire station in any of
the eight tracts. (The cost is far less for tract 5 because the current fire station already is there so only a modest
renovation is needed if the decision is made to retain a fire station there.)

The objective now is to determine which tracts should receive a fire station to minimize the total cost of the
stations while ensuring that each tract has at least one station close enough to respond to a fire in no more than 10
minutes.

Problem
Southwestern Airways needs to assign its crews to cover all its upcoming flights. We will focus on just one portion of
this problem, namely, the problem of assigning three crews based in San Francisco (SFO) to the 11 flights shown in
Figure below. Thus, each crew needs to be assigned to a sequence of flights that begins and ends in San Francisco.
Furthermore, the different sequences of flights for these three crews need to “cover” (i.e., include) all 11 flights.

The arrows show the 11 Southwestern Airways flights that need to be covered by the three crews based in San
Francisco. These 11 flights are listed in the first column of the Table below. The other 12 columns show the 12
feasible sequences of flights for a crew. The numbers in each column indicate the order of the flights. For example,
sequence 4 says for one crew to begin with flight 1 out of San Francisco, then take flight 4, then take flight 6, and then
finally take flight 8 back to San Francisco. This sequence thereby covers 4 of the 11 flights, so the other two
sequences for the other two crews would need to cover the remaining 7 flights

Feasible Sequence of Flights

Flights 1 2 3 4 5 6 7 8 9 10 11 12
1. SFO–LAX 1 1 1 1
2. SFO–DEN 1 1 1 1
3. SFO–SEA 1 1 1 1
4. LAX–ORD 2 2 3 2 3
5. LAX–SFO 2 3 5 5
6. ORD–DEN 3 3 4
7. ORD–SEA 3 3 3 3 4
8. DEN–SFO 2 4 4 5
9. DEN–ORD 2 2 2
 10. SEA–SFO 2 4 4 5
11. SEA–LAX 2 2 4 4 2
Cost, $1,000s 2 3 4 6 7 5 7 8 9 9 8 9

The key requirement is that (at most) three of the sequences need to be chosen (one per crew) in such a way that
every flight is covered. (It is permissible to have more than one crew on a flight, where the extra crews would fly as
passengers, but union contracts require that the extra crews still be paid for their time as if they were working.) The
cost of assigning a crew to a particular sequence of flights is given (in thousands of dollars) in the bottom row of the
table. The objective is to minimize the total cost of the crew assignments that cover all the flights.

Problem

Speedy Delivery provides two-day delivery service of large parcels across the United States. Each morning at each
collection center, the parcels that have arrived overnight are loaded onto several trucks for delivery throughout the
area. Since the competitive battlefield in this business is speed of delivery, the parcels are divided among the trucks
according to their geographical destinations to minimize the average time needed
to make the deliveries.
On this particular morning, the dispatcher for the Blue River Valley Collection Center, Sharon Lofton, is hard at work.
Her three drivers will be arriving in less than an hour to make the day’s deliveries. There are nine parcels to be
delivered, all at locations many miles apart. As usual, Sharon has loaded these locations into her computer. She is
using her company’s special software package, a decision support system called Dispatcher.
The first thing Dispatcher does is use these locations to generate a considerable number of attractive possible routes
for the individual delivery trucks. These routes are shown in the table below (where the numbers in each column
indicate the order of the deliveries), along with the estimated time required to traverse the route.

1 2 3 4 5 6 7 8 9 10
Location Attractive Possible Route
A 1 1 1
B 2 1 2 2 2
C 3 3 3 3
D 2 1 1
E 2 2 3
F 1 2
G 3 1 2 3
H 1 3 1
I 3 4 2
Time (hours) 6 4 7 5 4 6 5 3 7 6

Dispatcher is an interactive system that shows these routes to Sharon for her approval or modification. (For
example, the computer may not know that flooding has made a particular route infeasible.) After Sharon approves
these routes as attractive possibilities with reasonable time estimates, Dispatcher next formulates and solves a BIP
model for selecting three routes that minimize their total time while including each delivery location on exactly
one route.

Problem
The Fly-Right Airplane Company builds small jet airplanes to sell to corporations for use by their executives.
To meet the needs of these executives, the company’s customers sometimes order a custom design of the
airplanes being purchased. When this occurs, a substantial start-up cost is incurred to initiate the production
of these airplanes.
Fly-Right has recently received purchase requests from three customers with short deadlines. However,
because the company’s production facilities already are almost completely tied up filling previous orders, it
will not be able to accept all three orders. Therefore, a decision now needs to be made on the number of
airplanes the company will agree to produce (if any) for each of the three customers.
The relevant data are given in the next table. The first row gives the start-up cost required to initiate the
production of the airplanes for each customer. Once production is under way, the marginal net revenue
(which is the purchase price minus the marginal production cost) from each airplane produced is shown in
the second row. The third row gives the percentage of the available production capacity that would be used
for each airplane produced. The last row indicates the maximum number of airplanes requested by each
customer (but less will be accepted).

Fly-Right now wants to determine how many airplanes to produce for each customer (if any) to maximize the
company’s total profit (total net revenue minus start-up costs). Formulate and solve a spreadsheet model
with both integer variables and binary variables for this problem.