Name:

MATP6620/DSES6770
Combinatorial Optimization and Integer Programming
Spring 2007

Final Exam, Tuesday, May 8, 2007.

Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts three hours.














Q1           /56
Q2           /28
Q3           /16
Total    /100

  1. (56 points; each part is worth 7 points)
    1. Show that the following matrix $M$ is not totally unimodular:

      \begin{displaymath} M = \left[ \begin{array}{rrr} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{array}\right] \end{displaymath}

    2. Show that the constraints
      $\displaystyle x_1 + x_2$ $\textstyle =$ $\displaystyle 1$ (1)
      $\displaystyle x_1 + x_3$ $\textstyle \leq$ $\displaystyle 1$ (2)
      $\displaystyle x_2 + x_3$ $\textstyle \leq$ $\displaystyle 1$ (3)
      $\displaystyle x_i$   $\displaystyle \mbox{binary, } i=1,2,3$ (4)

      imply $x_3=0$.
    3. Given (1)-(4), what is the Chvatal rank of the valid inequality $x_3 \leq 0$?

      (this page intentionally left blank)

    4. 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 $e$. 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. Using the earlier parts of this question, show that the optimal integral multicommodity flow has value equal to 27.

    5. Show that the optimal solution to the linear programming relaxation of the multicommodity flow problem in part 1d does not give the optimal solution to the integral multicommodity flow problem.

      (this page intentionally left blank)

    6. A Lagrangian relaxation for the integer multicommodity flow problem in part 1d 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?

    7. How does the optimal value of the Lagrangian dual problem compare with the value of the LP relaxation of the integer multicommodity flow problem in part 1d?

      (this page intentionally left blank)

    8. A version of the integer multicommodity flow with lower bound feasibility problem can be stated
      Given a directed graph $G=(V,E)$, commodities $1,\ldots,k$ each with a single origin and destination and with available supply $d_i$, upper bounds $u_e$ for the total flow on arc $e$, and a positive number $Q$, does there exist an integer multicommodity flow of size at least $Q$?
      Show this problem is NP-Complete, using the Node Packing with lower bound feasibility problem or otherwise. (The node packing with lower bound feasibility problem can be stated:
      Given a graph $G=(U,F)$ and a positive integer $P$, find a node packing of cardinality at least $P$.
      You can assume this problem is NP-Complete.)

    (this page intentionally left blank)

  2. (28 points)
    Consider the following nonlinear integer programming problem:

    \begin{displaymath} \begin{array}{lrcrcl} \max & 7 x_1^2 x_2 x_3 & + & 3 x_2 x_3... ...eq & 3 \\ &&& x_i & & \mbox{binary, } i=1,\ldots,4 \end{array}\end{displaymath}

    1. (20 points) The nonlinear terms can be replaced by binary variables, for example we can use $z_4$ instead of $x_3x_4$ in the first constraint. By introducing extra binary variables, model this problem as an equivalent integer linear program. Try to make the LP relaxation strong, but do not eliminate or fix any of the variables $x_i$. Argue why your formulation is equivalent to the original problem.
    2. (8 points) Solve the problem.

    (intentionally left blank)

  3. (16 points)
    Let $S:=\{ x \in I\!\!B^3 : -2x_1 + 3x_2 + 4x_3 \leq 3 \}$ and $S^0 := \{x \in S : x_1 = 0 \}$.
    1. (6 points) Give an inequality description of the convex hull of $S$.
    2. (10 points) For any two scalars $u$ and $v$, the set $S^0$ can be written:

      \begin{displaymath} S^0 = \{x \in I\!\!B^3 : x_1=0, x_2 + vx_3 \leq 1, -x_2 + ux_3 \leq 0, x_3 \leq 0 \}. \end{displaymath}

      Show that there is only one choice of $v$ for which the lifted version of the constraint $x_2+vx_3 \leq 1$ defines a facet of $S$.

    (this page deliberately left blank)


John Mitchell
2009-03-05