CS/ECE/ISyE 524
Introduction to Optimization
Fall 2024
Homework 2: Linear Programs, Minimax and Network Flows
Due date: Friday October 4, 2024
1. [5 points] Polyhedron modeling. We saw that the set of x such that Ax ≤ bwhere A ∈ Rm ×n and b ∈ Rm describes a polyhedron. For each polyhedron below, find a matrix A and vector b such that Ax ≤ b describes the polyhedron. Hint: since each inequality describes a different face, m should be equal to the number of faces. Make sure the inequalities go the right way!
(a) Regular cube centered at the origin with vertices at (±1, ±1, ±1).
(b) Regular octahedron centered at the origin with vertices at (±1, 0, 0), (0, ±1, 0), (0, 0, ±1).
2. [10 points] Museum site planning. A cite wants to built a new technical museum, and need to decide which plot of land it should be built on. The aerial plans of two potential sites are shown in the figure below (in units of feet). The museum will have a circular footprint and law mandates that there be at least 50 feet of clearance between the building and any edge of the site. Which site they should choose, where in the plot should it be located (i.e. what is the optimal location of the center of the museum), and what is the optimal radius going to be?
a) Write down the mathematical model of the optimization problem to identify the optimal location of the museum for a given site. Include descriptions of the decision variables, constraints, ob- jective function and problem parameters. Note: We recommend to first write down an abstract mathematical formulation of the problem that represent the optimization problem to be solved for either of the two sites, and then define different input parameters to specify the specific instances related to Site 1 and 2.
b) Implement the problem in Julia using the provided template HW2-Q2 .ipynb. The output of the problem should be the optimal location and optimal radius of the museum. (Note: There is no submission for this question on Canvas.)
c) What is the optimal location and radius for Site 1? What is the optimal location and radius for Site 2? Which site can fit a larger museum?
d) Upload your Julia notebook to Canvas. Code your problem such that it will run for other potential sites (also be defined by straight lines in a similar manner as Site 1 and 2).
3. [10 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 first 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 figure out their availability. Here is the data:
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.
a) Write down the mathematical optimization model for this problem, including a desription of the decision variables, constraints and parameters of the problem.
b) Implement the problem in Julia and determine whether there exists a feasible solution. See hw2-q3-data .ipynb for the data.
c) If the problem is feasible, print out a calendar for the candidate that lists who they will be meeting at each time slot.
4. [10 points] 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.
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.
As always, we recommend solving this problem in the following steps:
(1) Formulate the optimization problem with decision variables, parameters, constraints and objective.
(2) Implement your problem in code and solve it with an appropriate solver.
(3) Analyze your results.
5. [10 points] The chess problem. A small joinery makes two different sizes of boxwood chess sets. The small set requires 3 hours of machining on a lathe, and the large set requires 2 hours. There are four lathes with skilled operators who each work a 40 hour week, so we have 160 lathe-hours per week. The small chess set requires 1kg of boxwood, and the large set requires 4kg. Unfortunately, boxwood is scarce and only 200 kg per week can be obtained. When sold, each of the large chess sets yields a profit of $8, and one of the small chess set has a profit of $5. The problem is to decide how many sets of each kind should be made each week so as to maximize profit.
Solve the following questions by hand, and upload your solution to Canvas:
i) Write out the primal LP. Plot the feasible set and solve the LP graphically. Be sure to label the axes and indicate units. Label the optimal point and find the optimal objective.
ii) Derive the dual problem. Repeat all the same steps as in part a), and verify that the optimal dual objective is the same as the primal objective.