MATP6620/DSES6770
Combinatorial Optimization and Integer Programming
Fall 2005

Final Exam, Friday, December 16, 2005.

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.

1.

(30 points; each part is worth 10 points)
Consider the knapsack problem

$$\begin{array}{lrcrcrcrcrclr} \max & 23x_1 & + & 17x_2 & + & ... ...lticolumn{11}{c}{x_i \in \{0,1\}, \; i=1,\ldots, 5} \end{array}$$

Let P denote the feasible region of (KP).

(a)

Recall that a cover is a set of variables x_j whose constraint coefficients a_j add up to more than b. Any feasible solution cannot have all of these x_j=1. Give three minimal cover inequalities satisfied by all feasible solutions to (KP). (Note: there are more than three minimal cover inequalities for this problem.)

(b)

The inequality

$$x_1 + x_2 + x_4 + x_5 \leq 2$$

is valid for $P \cap \{x \in I\!\!R^5: x_3=0\}$ Lift this inequality to give a valid inequality for P.

(c)

Let s denote the slack in the original knapsack constraint, and let s_i=1-x_i for $i=1,\ldots,5$. The optimal solution to the LP relaxation is to take x₁=x₂=1, x₃=0.3, and x₄=x₅=0. One row of the optimal simplex tableau can be written

x₃ + 0.7x₄ + 0.5 x₅ - 0.6 s₁ - 0.5 s₂ + 0.1s = 0.3.

Show that the Gomory cutting plane procedure applied to this constraint gives a constraint equivalent to a cover inequality. Is it a minimal cover inequality?

2.

(50 points, each part is worth 10 points)
Let G=(V,E) be a graph with edge weights w_e and let $R \subseteq V$ be a set of required vertices. The Steiner tree problem is to find the minimum weight tree in G that includes every vertex in R. In the following complete graph on four vertices, vertices 1, 2, and 3 are required, so R={1,2,3}. Edge lengths are indicated.

(a)

A feasible solution to a Steiner tree problem can be obtained by finding a minimum spanning tree on the subgraph of G induced by the vertices in R. Show that the minimum spanning tree on this subgraph is not optimal for the Steiner tree problem on this graph.

(b)

A first attempt to formulate the Steiner tree problem on this graph as an integer programming problem is the following:

$$\begin{array}{lrcrcrcrcrcrclr} \min & 5\mbox{$x_{1,2}$ }& ... ...box{$x_{2,4}$ }, \mbox{$x_{3,4}$ }\mbox{ binary}} \end{array}$$

The upper bound constraints $x_e \leq 1$ are redundant in the LP relaxation, so the dual to the LP relaxation can be written

$$\begin{array}{lrcrcrclr} \max & y_1 & + & y_2 & + & y_3 \\... ... & \multicolumn{5}{r}{y_1, y_2, y_3} & \geq & 0 \end{array}$$

Show that the optimal value of the LP relaxation is 7.5, by finding primal and dual feasible solutions with this value.

(c)

 

i.

Why are the following constraints valid for the Steiner Tree Problem:

$$\begin{array}{rcrcrcrcrcrcl} \mbox{$x_{1,2}$ }& + & \mbox{... ...ox{$x_{1,4}$ }& + & \mbox{$x_{2,4}$ }&&& \geq & 1 \end{array}$$

ii.

Give a feasible integral solution to (IP) that violates one of these constraints and does not correspond to a Steiner tree.

(d)

  Let S be the set of incidence vectors of feasible solutions to the Steiner tree problem. The constraint

$$3\mbox{$x_{1,2}$ }+ 3\mbox{$x_{1,3}$ }+ 3\mbox{$x_{2,3}$ }+... ...x{$x_{1,4}$ }+ 2 \mbox{$x_{2,4}$ }+ 2 \mbox{$x_{3,4}$ }\geq 6$$ (1)

is valid for S. Show that adding this constraint to the LP relaxation of (IP) results in an optimal value of 9, and hence gives a proof that the optimal Steiner tree uses the edges (1,4), (2,4), and (3,4).

(e)

By considering the valid constraints

$$\begin{array}{rcrcrcrcrcrcl} \mbox{$x_{1,2}$ }& + & \mbox{... ...{$x_{2,4}$ }& + & \mbox{$x_{3,4}$ }& \geq & 2 \\ \end{array}$$

or otherwise, show that constraint (1) does not define a facet of S. (You may assume that S has dimension equal to 6.)

3.

(20 points; each part is worth 10 points)
We have an integer program of the form

$$\begin{array}{lrclr} \min & c^Tx \\ \mbox{s.t.} & Ax & \geq & b & \qquad (IP) \\ & x && \mbox{binary} \end{array}$$

where b>0 and c>0, and each nonzero element a_ij of A satisfies $a_{ij} \geq b_i$.

(a)

Show that the optimal solution to the LP relaxation of (IP) can be used to find a feasible integer solution.

(b)

Let p be the maximum number of nonzeroes in any row of A. Give a polynomial time algorithm to find a feasible integer solution that has value within a factor of p of the optimal value.