MATP6620/DSES6760
Combinatorial Optimization and Integer Programming

Final Exam, Spring 2001

Take Home Due: 5pm, Monday, 30 April, 2001.

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 office extension is 276-6915 and you can also reach me by email at mitchj@rpi.edu. I will have office hours Wednesday from 1-3pm and Friday 2-4pm. 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 a bipartite graph G=(V,E), where V can be broken into two parts U and W, and every edge in E has one endpoint in U and one in W. (Formally, $V=U\cup W$, $U\cap W =\emptyset$, and $e \in E$ implies that e=(i,j), where $i\in U$ and $j\in W$.) Note that we have not assumed that every vertex in U is adjacent to every vertex in W. Because this is a bipartite graph, the maximum cardinality matching problem can be solved by solving its linear programming relaxation

$$\begin{array}{lrcllr} \max & \sum_{(i,j) \in E} x_{ij} \\ ... ...l j \in W \\ & x_{ij} & \geq & 0, & (i,j) \in E \end{array}$$

where x_ij is one if edge (i,j) is in the matching, and zero otherwise. Every basic feasible solution to both (P) and its dual (D) is integral.

(a)

(5 points) What is the dual (D) to the linear program (P)? (Hint: The dual of a linear program of the form $\max\{c^Tx:Ax\leq b,x\geq 0\}$ is $\min\{b^Ty:A^Ty\geq c, y\geq 0\}$.)

(b)

(10 points) A node cover of G is a subset S of V such that every edge in E is incident to at least one vertex in S. What do the integral solutions to (D) correspond to? What do you conclude from strong duality?

(c)

(10 points) What are the complementary slackness conditions for the pair (P) and (D)? Interpret these conditions.

2.

(20 points)

(a)

(10 points) Let M=(N,F) be a matroid defined on the finite set N and with independent sets F. The dual matroid $\bar{M}$ to M can be defined as the independence system on the finite set N with its maximal independent sets equal to the complements of the maximal independent sets in M. Show that $\bar{M}$ is a matroid. (Note: The dual matroid is defined in a different way in Nemhauser and Wolsey. I want you to use the definition I've given you here to prove this result, and not to use the definition in the text.)

(b)

(10 points) A matric matroid M₁=(N₁,F₁) can be represented using a matrix: elements of the finite set N₁ correspond to columns of the matrix, and the independent sets in F₁ correspond to linearly independent subsets of the columns. A graphic matroid M₂=(N₂,F₂) can be represented using a graph: elements of the finite set N₂ correspond to edges of the graph, and the independent sets in F₂ correspond to acyclic subsets of the edges. Show that any graphic matroid is also a matric matroid.

3.

(30+10 points)   Let G be a complete graph on 2s vertices, for some integer $s\geq 3$. Let each edge e have weight c_e. The equipartition problem on this graph is to divide the vertices into two sets of size s so as to minimize the sum of the weights of the edges that have one endpoint in each set. One polyhedral representation of this problem requires defining variables

$$x_e := \left\{ \begin{array}{ll} 1 & \mbox{if the endpoint... ...ifferent sets} \\ 0 & \mbox{otherwise} \end{array} \right.$$

for each edge e.

(a)

(5 points)  Show that x must satisfy the equality $\sum_{e \in \delta(v)}x_e=s$ for each vertex v, where $\delta(v)$ denotes the set of edges incident to vertex v.

(b)

(5 points) Show that the dimension of the feasible region is no more than

$$\mbox{dim}(Q) \leq \left( \begin{array}{c}2s\\ 2\end{array} \right) - 2s.$$

(c)

(Extra credit: 10 points) Show that the dimension of the feasible region is exactly

$$\mbox{dim}(Q) = \left( \begin{array}{c}2s\\ 2\end{array} \right) - 2s.$$

(d)

(5 points)   Let C be a cycle of length 3 and let E(C) denote the edges of this cycle. Show that any feasible solution satisfies

$$\sum_{e \in E(C)} x_e \leq 2.$$

(e)

(5 points)   Let C be a cycle of length s+1 and let E(C) denote the edges of this cycle. Show that any feasible solution satisfies

$$\sum_{e \in E(C)} x_e \geq 2.$$

(f)

(10 points) Solve the instance of the equipartition problem contained in

http://www.rpi.edu/~mitchj/matp6620/final/equi.mod

and

http://www.rpi.edu/~mitchj/matp6620/final/equi8.dat

using a cutting plane method.

4.

(25 points) Another approach to the equipartition problem is to define a variable

$$w_{kj} := \left\{ \begin{array}{ll} 1 & \mbox{if vertex $j$\... ... is on side $k$ } \\ 0 & \mbox{otherwise} \end{array} \right.$$

where k takes the values 1 and 2, corresponding to the two sides of the equipartition. Let g^(p) denote the p-vector with every entry equal to one.

(a)

(8 points) Let W denote the 2 x 2s matrix whose (k,j)th entry is w_kj. Show that the entries of W satisfy Wg^(2s)=sg⁽²⁾ and W^Tg⁽²⁾=g^(2s).

(b)

(8 points) Let X denote the 2s x 2s matrix whose (i,j)th entry is the variable x_ij defined in Question 3 corresponding to the edge e=(i,j). Show that E-X=W^TW for any feasible equipartition, where E denotes a matrix whose every entry is one.

(c)

(9 points) Show that an SDP relaxation of the equipartition problem is:

$$\begin{array}{lrcl} \min_Z & \frac{1}{2}C \bullet E - \frac{... ...& = & 1 \\ & Z & \succeq & 0 \mbox{ and symmetric} \end{array}$$

where Z is a 2s x 2s matrix and C_ij=c_e when the edge e=(i,j). How does the matrix Z relate to the matrices X and W given earlier? How can we exploit the results of Question 3 in this SDP formulation? What have we relaxed to arrive at this formulation?