Description

VG441 Supply Chain Management
Midterm II

The exam paper has 4 pages in total.

VG441 Supply Chain Management Midterm/Final Exam

Please enter grades here:

Exercises No.
题号 Points
得分 Grader’s Signature
流水批阅人签名
1
2
3
4
5
6
7
8
9
10
Total 总分

VG441 Take-Home Midterm II
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 Pi∈S fi + Pj∈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 Xfiyi + X dijxij
i∈F i∈F,j∈D
s.t. Xxij ≥ 1 ∀j ∈ D
i∈F
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