Homework 3: Network flows and duality

CS/ECE/ISyE 524 Introduction to Optimization
Homework 3: Network flows and duality

See the course website for instructions and submission details.
1. [10 pts] Doodle scheduling. Doodle Inc. is looking to interview a candidate for a new software
engineer position at their company. It works like this: the interview (10 AM to 3 PM) is divided into
a number of 20-minute time slots that may be used for 1-on-1 meetings with the candidate. There is
also a one-hour time slot in the middle of the day where 3 employees take the candidate out for lunch.
It would be nice for all 15 senior employees to meet with the candidate at some point during the
day, but everybody has a busy schedule so it’s not clear whether this will be possible. A doodle poll
(obviously) was sent to the 15 senior employees to figure out their availability. Here is the data:
10:00 10:20 10:40 11:00 11:20 11:40 Lunch 1:00 1:20 1:40 2:00 2:20 2:40
Manuel 0 0 1 1 0 0 0 1 1 0 0 0 0
Luca 0 1 1 0 0 0 0 0 1 1 0 0 0
Jule 0 0 0 1 1 0 1 1 0 1 1 1 1
Michael 0 0 0 1 1 1 1 1 1 1 1 1 0
Malte 0 0 0 0 0 0 1 1 1 0 0 0 0
Chris 0 1 1 0 0 0 0 0 1 1 0 0 0
Spyros 0 0 0 1 1 1 1 0 0 0 0 0 0
Mirjam 1 1 0 0 0 0 0 0 0 0 1 1 1
Matt 1 1 1 0 0 0 0 0 0 1 1 0 0
Florian 0 0 0 0 0 0 0 1 1 0 0 0 0
Josep 0 0 0 0 0 0 1 1 1 0 0 0 0
Joel 1 1 0 0 0 1 1 1 1 0 0 1 1
Tom 1 1 1 0 1 1 0 0 0 0 0 1 1
Daniel 0 1 1 1 0 0 0 0 0 0 0 0 0
Anne 1 1 0 0 1 1 0 0 0 0 0 0 0
In the table, a 1 means that the employee is available at the indicated time, while a 0 means that they
are unavailable. Determine whether a feasible interview schedule exists. If so, print out a calendar for
the candidate that lists who they will be meeting at each time slot.
2. [10 pts] Car rental. A small car rental company has a fleet of 94 vehicles distributed among its 10
agencies. The location of every agency is given by its geographical coordinates x and y in a grid based
on miles. We assume that the road distance between agencies is approximately 1.3 times the Euclidean
distance (as the crow flies). The following table indicates the coordinates of all agencies, the number
of cars required the next morning, and the stock of cars in the evening preceding this day.
Agency number 1 2 3 4 5 6 7 8 9 10
x coordinate 0 20 18 30 35 33 5 5 11 2
y coordinate 0 20 10 12 0 25 27 10 0 15
Required cars 10 6 8 11 9 7 15 7 9 12
Cars present 8 13 4 8 12 2 14 11 15 7
Supposing the cost for transporting a car is $0.50 per mile, determine the movements of cars that allow
the company to re-establish the required numbers of cars at all agencies, minimizing the total cost
incurred for transport.
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
3. [10 pts] Building a stadium. A town council wishes to construct a small stadium in order to
improve the services provided to the people living in the district. After the invitation to tender, a local
construction company is awarded the contract and wishes to complete the task within the shortest
possible time. All the major tasks are listed in the following table. Some tasks can only start after the
completion of certain other tasks, as indicated by the “Predecessors” column.
Task Description Duration
(in weeks) Predecessors
Maximum
reduction
(in weeks)
Cost of
reduction
($1k/wk)
1 Installing the construction site 2 none 0 –
2 Terracing 16 1 3 30
3 Constructing the foundations 9 2 1 26
4 Access roads and other networks 8 2 2 12
5 Erecting the basement 10 3 2 17
6 Main floor 6 4,5 1 15
7 Dividing up the changing rooms 2 4 1 8
8 Electrifying the terraces 2 6 0 –
9 Constructing the roof 9 4,6 2 42
10 Lighting of the stadium 5 4 1 21
11 Installing the terraces 3 6 1 18
12 Sealing the roof 2 9 0 –
13 Finishing the changing rooms 1 7 0 –
14 Constructing the ticket office 7 2 2 22
15 Secondary access roads 4 4,14 2 12
16 Means of signalling 3 8,11,14 1 6
17 Lawn and sport accessories 9 12 3 16
18 Handing over the building 1 17 0 –
And now, the problems:
a) What is the earliest possible date of completion for the construction? Note that the last two
columns of the table are not relevant for this part of the problem.
b) For some of the tasks, the builder may employ additional workers and rent more equipment to
cut down on the total time. The last two columns of the table show the maximum number of
weeks that can be saved per task and the associated additional cost per week incurred by the
extra work. Plot a trade-off curve that shows extra cost as a function of the number of weeks
early we wish the stadium to be completed.
c) The town council wants the builder to expedite the project. As an incentive, the council will pay
a bonus of $30k/week for each week the work finishes early. When will the project be completed
if the builder is acting in a way that maximizes his profit?
4. [10 pts] Dual interpretation. Suppose t ∈ [0, 2π] is a parameter. Consider the following LP:
minimize
p,q,r,s
p + q + r + s
subject to: p − r = cos(t)
q − s = sin(t)
p, q, r, s ≥ 0
a) Plot the optimal objective of this LP as a function of t. Can you explain what you see?
Hint: separately consider the cases where cos(t) and sin(t) are positive or negative (four cases).
b) Find the dual LP and interpret it geometrically. Does this agree with the solution of part a)?
2 of 2