Homework 3: Minimax and Network Flows

    1. 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 gure 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. See hw3data.ipynb for the data.


    2. Car rental. A small car rental company has a eet 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 ies). 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    Steve Wright,    Spring 2021


    3. 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. See hw3data.ipynb for the data.



Duration

Maximum
Cost of
Task
Description

Predecessors
reduction
reduction


(in weeks)







(in weeks)
($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  oor
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 o  ce
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
{







    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) 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 nishes early. To accomplish this, 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. When will the project be completed if the builder is acting in a way that maximizes his pro t?
























2 of 2