MATP6620 / DSES6760
Combinatorial Optimization and Integer Programming
Homework 6.

Due: Thursday, April 23, 2009.

  1. Nemhauser and Wolsey, page 346, question 14, parts (i), (ii), (iii), and (v).

  2. Use subgradients to show that the optimal solution to the Held-Karp 1-tree Lagrangian dual problem is $\lambda=0$ for the traveling salesman problem on the graph with edge costs given below:

    \begin{displaymath} \begin{array}{r\vert rrrrrrrr} & 1 & 2 & 3 & 4 & 5 & 6 & 7 &... ...5 & 5 & - & 5 \\ 8 & 9 & 9 & 9 & 1 & 5 & 5 & 5 & - \end{array}\end{displaymath}

  3. The directed graph $G=(V,E)$ is as follows:

    \begin{picture}(200,220)(0,-10) \put(0,0){\circle{20}} \put(0,200){\circle{20}} ... ... \put(50,58){2} \put(150,59){1} \put(120,132){17} \put(175,183){3} \end{picture}

    One unit of commodity A must be shipped from $b$ to $c$ and one unit of commodity B must be shipped from $f$ to $g$. The flows must be integral. The cost of shipping one unit of flow along an arc is indicated in the figure. The cost is the same for each commodity. Each arc $e \in E$ in the graph has capacity equal to one; this is the maximum total flow along the arc for the combination of the two commodities. 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? How does the optimal value of the Lagrangian dual problem compare with the value of the LP relaxation of the integer multicommodity flow problem?

  4. Consider the mixed integer programming problem $(MIP)$:

    \begin{displaymath} \begin{array}{lrrrrrrcl} \max & 8x_1 & +9x_2 & +5x_3 & +6x... ...j & \geq & 0 \\ &&&&&& y_i && \mbox{binary} \\ \end{array} \end{displaymath}

    Solve this problem using Bender's decomposition. (Take the problem

    \begin{displaymath} \begin{array}{lrrrcl} \max & z & -15y_1 & -10y_2 \\ \mbo... ...} & z &&& \leq & 28 \\ &&& y_i && \mbox{binary} \end{array} \end{displaymath}

    as the initial relaxation $(RMP)$.)

 John Mitchell
 Amos Eaton 325
 x6915.
 mitchj at rpi dot edu
 Office hours: Office hours: Mondays, 1-3pm, or by appointment.
 I will be out of town on April 20-22.


John Mitchell
2009-04-13