discrete optimization
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. 1 3 2 4 5 Figure 1: • Is (V (G),F) a matroid? Why? • Recall that the associated independence polytope is defined as PV (G),F = { x ∈ RV (G) ∣∣∣∣ x(S) ≤ r(S) ∀ S ⊆ V (G),xv ≥ 0 ∀ v ∈ V (G) } Write down the defining inequalities for PV (G),F . Eliminate the redundant ones. • How much is the maximum of 5x1 + 7x2 + 3x4 over PV (G),F? 1 Problem 3: Consider the graph G = (V,E) on Figure 2. 1 2 3 4 5 6 7 8 9 9 10 9 11 9 11 7 9 4 8 10 10 11 11 3 10 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) # 3 13500 5 27800 11 3900 7 9750 8 15250 9 1700 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: Julie 11 19 18 19 17 John 27 23 29 27 29 Jim 39 37 31 29 43 Jonathan 39 18 11 27 39 Jack 47 33 39 21 39 2 1 3 2 4 6 5 7 8 3 5 3 4 6 5 4 2 5 6 7 3 9 2 1 7 54 3 Figure 3: 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