67.612/92.672/66.612
Combinatorial Optimization and Integer Programming

Final Exam, Spring 1997

Take Home Due: 12 noon, Friday, 9 May, 1997.

This is to be all your own work. You may use any result from class, homeworks, or the books and papers on reserve in the library. Do not consult anybody or anything else. I can dispense hints to help you if you are stuck. My phone numbers are 276-6915(O) and 346-2811(H). You can also reach me by email at mitchj@rpi.edu. I will have office hours each Thursday from 2-5pm. I will be out of town between Friday, 2 May and Wednesday, 7 May, inclusive. The exam consists of four questions and is worth 100 points.

In order that I can display grades, please write a 4 digit number on the front of your solution set.

1.

(25 points) Consider the complete undirected graph G=(V,E) on n vertices. A travelling salesman tour on this graph can be described as a collection of edges T such that the graph G'=(V,T) is connected, T contains n edges, and each vertex is adjacent to two edges. Let c_e be the cost of edge e in E. The travelling salesman problem is to find the minimum weight tour, that is

$$\min\{\sum_{e \in T}c_ex_e : \mbox{$T$\space is a tour}\}.$$

Let $\delta(i)$ denote the edges which are incident to vertex i.

(a)

(10 points) Verify that the following problem is a Lagrangian relaxation of the travelling salesman problem:

$$\begin{array}{llr} \min & \sum_{e \in T}c_ex_e + \sum_{i ... ...panning tree together with one additional edge.} \end{array}$$

(b)

(5 points) What would it imply if the optimal solution to $LR(\lambda)$ was a tour?

(c)

(10 points) Solve $LR(\lambda)$ for the graph with edge lengths as in the following table, with vertex weights $\lambda_1=2$, $\lambda_2=4$, $\lambda_3=6$, $\lambda_4=4$, $\lambda_5=0$, and $\lambda_6=2$. (You may assume that the solution to a problem of the form

$$\min\{\sum_{e \in T}w_ex_e : \mbox{$T$\space is a spanning tree together with one additional edge}\}$$

is obtained by finding the minimum weight spanning tree and then adding in the remaining shortest edge.)

$$\left[ \begin{array}{rrrrrr} -- & 12 & 20 & 20 & 17 & 15 \\ ... ...{c} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \end{array} \right.$$

2.

(25 points; each part is worth 5 points.) Given the complete graph K_n=:(V,E) on n vertices and edge weights w_e on the edges, a clustering of the vertices is obtained by choosing an integer p and a partition of the vertices into p sets $V_1,\ldots,V_p$ satisfying:

• $V_i \cap V_j = \emptyset$ for $1\leq i < j \leq p$.
• $\cup_{i=1}^p V_i=V$.

The incidence vector of this clustering is defined by

$$x_e = \left\{ \begin{array}{ll} 1 & \mbox{if the two endpoi... ... same set $V_j$ } \\ 0 & \mbox{otherwise} \end{array} \right.$$

The clustering problem for this set of edge weights is then

$$\begin{array}{ll} \max & z:=\sum_{e\in E}w_ex_e \\ \mbox{... ...{ is the incidence vector of a} \mbox{ clustering} \end{array}$$

The edge weights w_e can be positive or negative. If all the edge weights are positive, the optimal solution is to set p=1 and put all the vertices in one set, giving a value $z=\sum_{e \in E}w_e$. If all the edge weights are negative, the optimal solution is to set p=n and put each vertex in its own set, giving a value z=0. The weights w_e measure a ``distance'' between two vertices: the larger this value, the more likely the vertices should be in the same subset V_j, and if w_e is very negative, the vertices will probably be in different sets in the optimal solution.

Let Q be the set of incidence vectors of clusterings for K_n.

(a)

Show that the dimension of Q is n(n-1)/2, ie, Q is full dimensional.

(b)

Show that the inequality

$$x_{ij} + x_{jk} - x_{ik} \leq 1, \;\; 1 \leq i <j<k \leq n$$ (1)

is valid for any point in Q.

(c)

Show that inequality $(\ref{eqn.cluster})$ defines a facet of the convex hull of Q.

(d)

 Take n=4. Choose edge weights w_e so that the optimal solution to the following relaxation of the clustering problem is not in the convex hull of Q:

$$\begin{array}{lccll} \max & \sum_{e \in E} w_e x_e \\ \m... ... \leq \;\;\; x_e & \leq & 1 & \mbox{ for } e \in E \end{array}$$

(e)

Find a valid inequality that cuts off the point you found in part (2d).

3.

(25 points) Consider the travelling salesman problem (TSP) on the complete undirected graph. Let X be an instance of the travelling salesman problem, let OPT(X) be the optimal value of this instance, and let A be a polynomial time algorithm for the TSP which finds a tour of length A(X). We know that (unless $\cal{P}=\cal{NP}$) algorithm A will not find the optimal solution to every instance X. Let r be a given constant, $1 < r < \infty$. Show that we can not even guarantee $A(X) \leq rOPT(X)$, unless $\cal{P}=\cal{NP}$.

If the edge lengths c_ij satisfy the triangle inequality $c_{ij}+c_{jk}\geq c_{ik}$ for every three vertices i, j, and k then Christofides Heuristic generates a tour that is guaranteed to be no more than 1.5 OPT(X). How does your earlier proof break down if the edge lengths must satisfy the triangle inequality?

4.

(25 points) Consider the mixed integer programming problem (MIP):

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

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

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

as the initial relaxation (RMP).)