MATP6620/DSES6760
Combinatorial Optimization and Integer Programming

Final Exam, Spring 1999

Take Home Due: 5pm, Tuesday, 4 May, 1999.

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 Thursday from 1-2pm and Monday 2-5pm. The exam consists of five 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.

(20 points)

(a)

(5 points) How is the optimal solution to an instance of the traveling salesman problem altered if a constant k is added to every edge length?

(b)

(10 points) Show that any instance of the traveling salesman problem can be transformed into an equivalent instance satisfying the triangle inequality.

(c)

(5 points) Why doesn't the Christofides heuristic applied to the equivalent instance give a solution to the original instance that is within a factor of 3/2 of optimality?

2.

(20 points) Consider a graph G=(V,E). Let $n=\mid V \mid$. Let the set of node packings on G be $S=P \cap Z^n$, where $P = \{x \in \Re_+^n : x_i + x_j \leq 1 \; \forall (i,j) \in E \}$. Show that the Chvatal rank of a clique constraint $\sum_{j \in C} x_j \leq 1$ is $O(\log(\mid C \mid))$, where C is a clique of the graph. (See question 3 for the definition of a clique.)

3.

(20 points) You are given a graph G=(V,E), and weights w_v on the vertices v in V. Let m be the number of vertices in V. A clique in G is a subset U of V where every vertex in U is adjacent to every other one in U. The max-clique problem is to find the clique U in G with largest weight $\sum_{v \in U} w_v$. This can be written as the following integer programming problem:

$$\begin{array}{lccll} \max & \sum_{v \in V} w_v x_v \\ \m... ... 0 \mbox{ or } 1 & \mbox{ for all vertices $i$ } \end{array}$$

Let S be the set of incidence vectors of cliques.

(a)

(5 points) Show that the dimension of S is m. (Note: The empty set is a clique in G.)

(b)

(5 points) Let W be a maximal node packing in G. Show that the inequality

$$\sum_{v \in W} x_v \leq 1$$ (1)

is a facet defining inequality for S.

(c)

(10 points) Find the maximum cardinality clique in the graph with ten nodes and with every edge except the following: (1,2), (1,3), (1,6), (2,3), (2,4), (3,4), (4,5), (4,7), (4,10), (5,6), (5,7), (5,8), (6,7), (6,8), (6,9), (7,8), (7,10), (8,9), and (9,10). (In the maximum cardinality problem, each vertex has weight w_v=1.) Prove your solution is optimal by looking at the linear programming relaxation of the clique problem and adding selected inequalities of the form (1). (The AMPL model file for the initial relaxation is in the file

http://www.math.rpi.edu/~mitchj/matp6620/finalq3.mod

and the data file is in

http://www.math.rpi.edu/~mitchj/matp6620/finalq3.dat.

You may not be able to get an integral solution to the relaxation. Do you need to?)

4.

(20 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).)

5.

(20 points) The solution to the MAXCUT problem on three vertices with edge weights c₁₂=1, c₁₃=2, c₂₃=4 is to place vertex 3 on one side of the cut and the other two vertices on the other side. The semidefinite programming relaxation that is used to solve this problem is

$$\begin{array}{lrcllr} \min & \mbox{trace}(CX) \\ \mbox{subj... ...& i=1,\ldots,3 & \qquad (SDP)\\ & X & \succeq & 0, \end{array}$$

where the final constraint requires that X be a symmetric positive semidefinite matrix, and C is given by

$$C = \left[ \begin{array}{rrr}0&1&2\\ 1&0&4\\ 2&4&0\end{array} \right] .$$

Recall that we obtain this relaxation by replacing the requirement that X=xx^T with the requirement $X\succeq 0$, and that $x_i=\pm 1$, depending on which side of the cut vertex i is on.

(a)

(5 points) Let $\hat{x}$ be the vector corresponding to the solution given above for our instance of MAXCUT. Let $\hat{X}=\hat{x}\hat{x}^T$. What is the value of $\hat{X}$ in (SDP)?

(b)

(15 points) The dual problem to (SDP) is

$$\begin{array}{llr} \max & \sum_{i=1}^3 Y_{ii} \\ \mbox{subject to} & C - Y \succeq 0 & \qquad (SDD), \end{array}$$

where Y is a diagonal matrix, so Y_ij=0 if $i\neq j$. The value of any dual feasible solution provides a lower bound on the optimal value of (SDP). You may assume that the optimal primal and dual solutions X^* and Y^* for (SDP) and (SDD) satisfy a variant of complementary slackness, namely, X(C-Y)=0, where the product is the usual matrix product, and so 0 here denotes a 3 x 3 matrix of zeroes. Use this to construct a matrix $\hat{Y}$ that shows that the matrix $\hat{X}$ solves (SDP).