Combinatorial Optimization and Integer Programming

Spring 2001

Midterm Exam, Thursday, March 8, 2001.

Please do all five 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 two hours.


(20 points) An instance d of a feasibility problem $X \in NP$ depends upon two positive integer parameters m and n. Assume d requires storage m2n in binary, and that we know an algorithm A which solves d in time 2m+n.
(10 points) Can we conclude X is in P?
(10 points) Assume we know in addition that $m\leq n$ for every instance d of X. What can we conclude now?
(20 points) Using the Hamiltonian path problem, or otherwise, show that the following problem is ${\cal N}{\cal P}$-complete.
Given a graph G=(V,E) and an integer k, is there a spanning tree T of G that has exactly k leaves?
(A leaf of a tree is a vertex of degree 1. The Hamiltonian path problem is: Given a graph G=(V,E), does there exist a path which visits all the vertices of G exactly once? You may assume that this problem is ${\cal N}{\cal P}$-complete.)     
Let $S:= \{ x \in I\!\!B^3: -x_1+x_2+3x_3 \leq 2\}$. Let $S^0:=S \cap \{ x \in I\!\!B^3: x_1=0\}$.
(5 points) Show that $x_2 \leq 1$ defines a facet of the convex hull of S0.  
 (5 points) Derive a valid inequality for S by lifting the valid inequality for S0 given in part 3a.
(5 points) Show that the inequality you derived in part 3b does not define a facet of the convex hull of S.
(5 points) Give an inequality description of the convex hull of S.
(20 points) We wish to solve the MAXCUT problem on a graph G=(V,E) with edge weights ce. Recall that we modeled this as an integer programming problem by introducing binary variables xe to indicate whether an edge is in the cut. Let S be the set of incidence vectors corresponding to cuts. These variables satisfied the constraints

x(F)-x(C\setminus F) \leq \vert F\vert-1
\end{displaymath} (1)

for any chordless cycle C, where F is a subset of C of odd cardinality. We are going to restrict our attention to K5, the complete graph on 5 vertices.
(5 points) Argue from first principles that any maxcut on K5 uses at most 6 of the edges of K5.
(10 points)  Show that the point $x_e=\frac{2}{3}$ for all edges e satisfies (1) for all chordless cycles C and corresponding subsets F. Show further that this point is not in the convex hull of the set of incidence vectors of cuts. What constraint does this suggest?
(5 points) How would you try to show that the constraint you defined in part 4b gives a facet of the convex hull of cuts? (Note: I do not want you to show that it is a facet; instead, I want you to tell me what points you might consider, and what you might try to do with those points. You may assume S is full dimensional.)
(20 points) Resolution is a technique used in logic to try to solve instances of SATISFIABILITY. It works by combining two clauses to generate an extra clause that must be satisfied by any solution to the instance. For example, consider the two clauses $x_1 \vee \bar{x}_2 \vee x_3$ and $\bar{x}_2 \vee \bar{x}_3 \vee x_4$. If x3 takes the value true then either x2 must be false or x4 must be true in order for the second clause to be satisfied. If x3 is false then either x1 must be true or x2 must be false in order for the first clause to be satisfied. It follows that any truth assignment satisfying the clauses $x_1 \vee \bar{x}_2 \vee x_3$ and $\bar{x}_2 \vee \bar{x}_3 \vee x_4$ must also satisfy the clause $x_1 \vee \bar{x}_2 \vee x_4$. We say in this case that the two clauses were resolved using x3.

In general, to resolve two clauses using variable xi, the clauses have the forms:

xi $\textstyle \vee$ $\displaystyle ( \bigvee_{j \in C_1^+} x_j ) \vee
( \bigvee_{j \in C_1^-} \bar{x}_j )$ (2)
$\displaystyle \bar{x}_i$ $\textstyle \vee$ $\displaystyle ( \bigvee_{j \in C_2^+} x_j ) \vee
( \bigvee_{j \in C_2^-} \bar{x}_j ).$ (3)

Any solution to these two clauses must also satisfy the resolved clause

( \bigvee_{j \in C_1^+ \cup C_2^+} x_j ) \vee
( \bigvee_{j \in C_1^- \cup C_2^-} \bar{x}_j ).
\end{displaymath} (4)

Note that it is not necessary that the four sets of indices C1+, C1-, C2+, and C2- be distinct.

In this question, we are going to investigate the representation of SATISFIABILITY as an integer programming problem. Thus, we introduce a 0-1 variable yi for each logical variable xi and we introduce an inequality for each clause. The clauses can be satisfied simultaneously if and only if the inequalities can be satisfied simultaneously.

(5 points) Assume the four sets C1+, C1-, C2+, and C2- are distinct. Show that the inequality corresponding to (4) is implied by the inequalities corresponding to equations (2) and (3).
(10 points) Now assume that $C_i^+ \cap C_j^- = \emptyset$ for any combination of i and j, but that either $C_1^+ \cap C_2^+ \neq \emptyset$ and/or $C_1^- \cap C_2^- \neq \emptyset$. Show that the resolved clause can be derived using one step of the Chvatal-Gomory rounding procedure.
(5 points) Find a fractional point that satisfies the inequalities corresponding to the clauses $x_1 \vee \bar{x}_2 \vee x_3$ and $\bar{x}_2 \vee \bar{x}_3 \vee x_4$ but which violates the inequality corresponding to the clause $x_1 \vee \bar{x}_2 \vee x_4$.

John E. Mitchell