Makeup for First Homework Set
Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.
Solutions are due by midnight on April 21, 2020 (SHARP!)
Problem 1: Let a ∈ Rn+ and b ∈ R+ be given parameters. Let us call a subset S ⊆ E = {1,2,…,n} independent if a(S) = j∈S aj ≤ b. We know that this defines an independence system.
• Consider n = 7, a = (1,1,1,2,3,4,6), b = 9, and X = {1,2,3,4,5,6,7}: What are the values of r(X) and ρ(X)?
• Consider the values/weights c = (2,2,3,4,1,5,6). What is the Best-in- Greedy independent set?
Problem 2: Consider the graph G = (V, E) on Figure 1. Let F ⊆ 2V (G) be the family of independent (stable) sets of G, that is vertex subsets that do not contain an edge inside.
12
3
45
Figure 1:
• Is (V(G),F) a matroid? Why?
• Recall that the associated independence polytope is defined as
V(G) x(S) ≤r(S) ∀S⊆V(G), PV(G),F = x∈R xv ≥0 ∀v∈V(G)
Write down the defining inequalities for PV (G),F . Eliminate the redundant ones.
• How much is the maximum of 5×1 +7×2 +3×4 over PV(G),F?
1
Problem 3: Consider the graph G = (V, E) on Figure 2. 1 9 2 11 3
10 99117
4 9 5 10 6
4 81011 11
7 3 8 10 9
Figure 2:
• What is the weight of the maximum-weight spanning tree?
• Compute the sequence of edges chosen by Kruskal’s algorithm.
Problem 4: Consider the following cutting stock problem, with input length L = 31. These 31-feet pieces are to be cut into smaller ones to fulfill the following orders:
length ordered (in feet) #
Use the AMPL model to solve this problem. What is the optimal solution?
Problem 5: You manage a lawfirm, and you have 5 new important cases, C1, C2, C3, C4 and C5, and five associates, Julie, John, Jim, Jonathan and Jack to assign. You play mock-trials with your associates in all five cases, and see the following chances:
3
5 11 7 8 9
13500
27800
3900
9750
15250
1700
Julie
J ohn Jim
J onathan J ack
11 19
27 23
39 37
39 18
47 33
2
18 19 17
29 27 29
31 29 43
11 27 39
39 21 39
245
35521
5
1 36678 3
6
27453
3
47
9
Figure 3:
4
where each entry in the matrix is the chance in % that the assigned associate will lose the trial. If all these cases expect to bring in the same amount if you win, and nothing if you loose, what is your best strategy to assign your five associates to these 5 cases, one to one? Run the Hungarian algorithm and document the steps it takes.
Problem 6: Consider the instance of the Chinese Postman problem shown in Figure 3. The edge traversing times are shown along the edges in minutes.
• Assume that the post office is in area 2. What is the optimal, time mini- mizing tour of the postman? How much time does he need to deliver all letters and get back to the post office?
• Assume that the post office is in area 5. What is now the time he needs to deliver all letters?
3