Due: Friday, April 29, 2011.
Penalty for late homeworks: 10% for each day or part of a day.

Nemhauser and Wolsey, page 347, question 16. (Consider the criteria listed in Q15 on page 346.)
Solve the Held-Karp 1-tree Lagrangian dual problem for the graph with edge costs given below: $| --|-1---2---3---4--5---6-- 1| - 10 9 14 5 14 2|10 - 11 10 7 10 3| 9 11 - 8 9 14 4|14 10 8 - 9 13 5| 5 7 9 9 - 8 6 14 10 14 13 8 -$
(Hint: The optimal Lagrangian multipliers are integral.)
The graph G = (V,E) is as follows:

One unit of commodity A must be shipped from c to k and one unit of commodity B must be shipped from h to l. The flows must be integral. The cost of shipping one unit of flow along an arc is one for each commodity, and the total capacity of each arc is also one. The capacity is the sum of the flow in both directions. A Lagrangian relaxation for the integer multicommodity flow problem could be constructed by placing the upper bound constraints on the arcs in the objective function. If the Lagrangian multipliers are set equal to zero, what is the value of the Lagrangian relaxation? Find a choice of Lagrangian multipliers for which the optimal solution to the Lagrangian relaxation gives the optimal solution to the multicommodity flow problem. How does the optimal value of the Lagrangian relaxation compare to the optimal value of the LP relaxation?

John Mitchell

Amos Eaton 325

x6915.

Office hours: Tuesday, Wednesday, 2-3pm.