Description
-
[2 points] Polyhedron modeling. We saw that the set of x such that Ax b where A 2 Rm n and b 2 Rm describes a polyhedron. For each polyhedron below, nd a matrix A and vector b such that Ax b describes the polyhedron. Hint: since each inequality describes a di erent face, m should be equal to the number of faces. Make sure the inequalities go the right way!
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2022
-
[3 points] Doodle scheduling. Doodle Inc. is interviewing a candidate for a 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. The rst 20-minute slot at 10 am should include two employees, one of which needs to be either Mirjam or Matt. There is also a one-hour time slot in the middle of the day where 3 employees take the candidate out for lunch.
The goal is that all the senior employees to meet with the candidate at some point during the day, and that the candidate has someone to meet in every time slot (but never meets anyone more than once). However, everybody has a busy schedule so it’s not clear whether this will be possible. A doodle poll (obviously) was sent to the 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
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
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
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
Christian
0
1
1
0
0
0
0
1
1
1
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.
As Doodle Inc’s hiring manager, it is your task to determine whether a feasible interview schedule exists.
-
[1 point] Write down the mathematical optimization model for this problem, including a desription of the decision variables, constraints and parameters of the problem.
-
[1.5 points] Implement the problem in Julia and determine whether there exists a feasible solution. See hw3data.ipynb for the data.
-
[0.5 points] If the problem is feasible, print out a calendar for the candidate that lists who they will be meeting at each time slot.
2 of ??
