Description
VG441 Take-Home Midterm II
You are encouraged to type your answer using LaTeX, but scanning document is acceptable. The due date
of this midterm is on Canvas. No late submission is allowable. It is also not allowed to ask any questions
to peers or Professor or TA since this is an exam. But you can post clarification questions on Piazza.
Bonus problem is optional to submit.
Problem 1 (Traveling Salesman Problem)
There are 6 cities that a salesman must visit (as a tour). The distance matrix is given by
City/City 1 2 3 4 5 6
1 0 10 100 50 33 66
2 10 0 22 86 952 3
3 100 22 0 6 86 2
4 50 86 6 0 5 4
5 33 952 86 5 0 9
6 66 3 2 4 9 0
Task 1: Run double tree algorithm on paper.
Task 2: Run Christofides’ algorithm on paper. (Try eyeballing minimum cost matching solution.)
Problem 2 (Knapsack)
Consider the following simple example of n = 4 items (each with a value and a size):
Sizes: s1 = 3, s2 = 3, s3 = 8, s4 = 5
Values: v1 = 4, v2 = 4, v3 = 6, v4 = 5
Finally, the bag size is B = 8.
Task 1: Run the exact dynamic program (ExactKS) on paper to solve this problem.
Task 2: Run the simple greedy algorithm (ranking via vi/si) and show that it is not optimal.
Problem 3 (Minimum Cost Set Cover)
The ground set (to be covered) is V = {e1, e2, . . . , e11, e12}. You are given 3 (overlapping) sets
S1 = {e1, e2, e3, e4, e5}
S2 = {e1, e2, e3, e6, e7}
S3 = {e4, e5, e8, e9, e10, e11, e12}
The cost of using S1 is 6. The cost of using S2 is 15. The cost of using S3 is 7. We want to cover the
ground set using minimum cost. A greedy algorithm would be as follows. In each iteration, for each
unselected set, see how many uncovered elements can be covered using this set, and compute the ratio
of cost to this number. Then rank these ratios and select the set with the smallest ratio.
Task 1: Run this greedy algorithm on paper.
Task 2: Is your greedy solution optimal? Can you eyeball a better solution?
Bonus Problem* (Facility Location)
We consider the following metric uncapacitated facility location problem. The input is given by
• Set D of demands
• Set F of facilities
• Metric distance function dij for every i ∈ F and j ∈ D
• Facility setup costs fi for every i ∈ F
The output should be S ⊆ F that minimizes P
i∈S
fi +
P
j∈D mini∈S dij .
In class, we have formulated this problem as a MILP. If we relax the binary decision variables to
continuous ones, we obtain the following linear programming relaxation, denoted by (P):
(P) min X
i∈F
fiyi +
X
i∈F,j∈D
dijxij
s.t. X
i∈F
xij ≥ 1 ∀j ∈ D
xij ≤ yi ∀i ∈ F, j ∈ D
xij , yi ≥ 0
Here xij is the fraction of demand j that is served by facility i, and yi
is the (continuous) decision of
whether facility i should be opened. Note that yi should be binary {0, 1} but we relax it to be yi ≥ 0.
Task 1: Assign dual variables αj for every demand j ∈ D, and dual variables βij for every (facility,
demand) pair. Derive the dual linear program (D) in terms of these α’s and β’s.
Task 2: Think of αj as the amount of money demand j is willing to contribute to the solution, and
βij as the amount of money demand j’s contributes towards opening facility i. Try to interpret the dual
linear program (D).
2
