15.082 Final Exam Spring 2003 Name Instructions. 1. Please answer all questions in the exam books that are provided. 2. Please budget your time carefully. It is often a good idea to read the entire exam first, so that you can first do the questions that take the least amount of time. 3. Point values are listed on each problem. 4. Questions crossed out in red cover topics not included on Midterm 2, Fall 2010.Part 1. (45 points) 1. (15 points, 2 points for parts a, b and c. 3 points for parts d, e and f.) Consider the following max flow problem given by the preflow push algorithm. The distance labels are given at left. The numbers above or below the nodes are the excesses. The numbers on the arcs are the residual capacities. 7054321ts24 53st23453602132321510218 a. Is the labeling of the nodes valid? Why or why not? b. What are the admissible arcs? c. Which nodes are active? d. If the highest level push algorithm is used, what is the next node selected? Perform push relabels on that node and stop after the first non-saturating push. Show intermediate steps. e. Suppose that excess scaling is used and that we are at the 8-scaling phase. So no node has an excess of more than 8, and each non-saturating push has at least 4 units of flow. According to the excess scaling algorithm given in class, which node(s) could be selected next for pushing? f. A potential function argument was used to prove the O(n2m) time bound in class and in the text. What was the potential function? Evaluate the potential function for the current preflow.2. (12 points) The following is a feasible flow during some iteration of a minimum cost flow problem. Assume that each lower bound on an arc flow is 0. Recall that the tail of arc (i, j) is node i and the head is node j. Tail Head Capacity Flow Cost 1 2 6 5 1 2 4 5 5 -2 4 3 7 4 2 1 3 7 5 2 2 3 4 4 3 a. (5 points) Write the residual network, and find a negative cost cycle in the residual network, and state the capacity of the cycle. If there is no negative cost cycle, then say so. b. (2 points). Use the fact that the flow given above is feasible to determine the supply/demand b(j) of each node j = 1, 2, 3, 4. c. (5 points) Does the above flow correspond to a spanning tree solution? If not, why not? If so, what is the basic feasible structure, the node potentials, and the reduced costs of the non-basic arcs? 3. (8 points, 4 points per part) Consider the network below for the minimum cost spanning tree problem. 6124 5384613572 a. What is the minimum cost spanning tree? List the arcs of the minimum cost spanning tree in the order in which they are added by Kruskal’s algorithm. You do not need to show steps of the algorithm. b. Consider Prim’s algorithm for the minimum cost spanning tree starting from node 1. List the arcs of the minimum cost spanning tree in the order they are added to the tree by Prim’s algorithm. You do not need to show the steps of the algorithm.4. (10 points, 5 points per part.) Consider the multicommodity flow problem in the diagram below. 6124530011132265 units Good 1Î5 units Good 1Î4 units Good 2Î4 units Good 2Î The arc numbers are costs. One needs to send 5 units of commodity 1 from node 1 to node 4. One needs to send 4 units of commodity 2 from node 3 to node 6. In addition, there are bundle constraints on arcs (1, 2), (2, 5), and (5, 6). u12 = 4, u25 = 6, and u56 = 3. a. Write the path formulation for this multicommodity flow problem. (This is the formulation that uses column generation, as discussed in the second lecture on multicommodity flows.) b. Suppose that the first restricted master problem consists of paths 1-4 and 3-6. What is the optimal solution to this restricted master problem, and what are the arc tolls that result? Assuming that the algorithm would add one path from each commodity, what paths would be added next to the restricted master? Please justify your answer.Part 2 (25 points) Modeling and transformations 5. (10 points) Consider a simple variant of the usual maximum flow problem in a network G = (N, A) in which there is a positive lower bound lij on the flow of each arc (i,j) as well as a positive upper bound uij on the flow. Rather than send the most amount of flow from s to t, the objective in this problem is to send the least amount of flow from s to t, while satisfying the lower bound constraints and conservation of flow at all nodes other than s and t. Explain how to solve this problem by two applications of a maximum flow algorithm. (HINT: First explain how to determine a feasible flow for the original problem by using one application of a maximum flow algorithm in a network G’ that is closely related to G.) 6. (15 points, 5 points per part). Consider the minimum cost network flow problem subject to a single side constraint. (, )* min ij ijij Azcx∈=∑ (0) su:( , ) :( , )bject to for ij ji ijij A j ji Axxbi∈∈N−=∑∑∈ (1) (,)ij ijij Atx T∈≤∑ (2) 0 for all ( , )ij ijxu ijA≤≤ ∈ (3) integralx (4) Assume that there is a feasible solution to the above integer program. a. What is the Lagrangian problem L(µ) if we associate a vector µ of multipliers with (1)? Is it true that L(µ) ≤ z* for all µ? State the Lagrange multiplier problem, and let L*1 denote the optimal solution to the Lagrange multiplier problem (see part c). b. What is the Lagrangian problem L(λ) if we associate a scalar λ for the single constraint (2)? Is it true that L(λ) ≤ z* for all λ? If not, what is true? Be careful about the sign of λ. State the Lagrange multiplier problem, and let L*2 denote the optimal solution to the Lagrange multiplier problem. (see part c). c. Let z’ be the optimal solution to the LP relaxation, that is the LP obtained by relaxing constraints (4) above. Can we conclude that z’ = L*1? Can we conclude that z’ = L*2. Justify your answer in both cases.Part 3. (30 points) Short answer. 7. (7 points). Suppose that a generalized flow problem on a network G = (N,A) has m arcs and n nodes, and that there is at least one cycle that is not a breakeven cycle. Suppose further that there is a feasible solution. First, describe what a breakeven cycle is. Next, describe what a basis structure is and tell how