Name:

MATP6620/DSES6770
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.

Q1
Q2
Q3
Q4
Q5
Total

1.

(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 m2ⁿ in binary, and that we know an algorithm A which solves d in time 2^m+n.

(a)

(10 points) Can we conclude X is in P?

(b)

(10 points) Assume we know in addition that $m\leq n$ for every instance d of X. What can we conclude now?

    
    

2.

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

3.

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\}$.

(a)

(5 points) Show that $x_2 \leq 1$ defines a facet of the convex hull of S⁰.  

(b)

 (5 points) Derive a valid inequality for S by lifting the valid inequality for S⁰ given in part 3a.

(c)

(5 points) Show that the inequality you derived in part 3b does not define a facet of the convex hull of S.

(d)

(5 points) Give an inequality description of the convex hull of S.

    
    

4.

(20 points) We wish to solve the MAXCUT problem on a graph G=(V,E) with edge weights c_e. Recall that we modeled this as an integer programming problem by introducing binary variables x_e 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$$ (1)

for any chordless cycle C, where F is a subset of C of odd cardinality. We are going to restrict our attention to K₅, the complete graph on 5 vertices.

(a)

(5 points) Argue from first principles that any maxcut on K₅ uses at most 6 of the edges of K₅.

(b)

(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?

(c)

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

    
         
    

5.

(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 x₃ takes the value true then either x₂ must be false or x₄ must be true in order for the second clause to be satisfied. If x₃ is false then either x₁ must be true or x₂ 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 x₃.

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

  

$$\vee ( \bigvee_{j \in C_1^+} x_j ) \vee ( \bigvee_{j \in C_1^-} \bar{x}_j )$$ x_i (2)

$$\bar{x}_i \vee ( \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 ).$$ (4)

Note that it is not necessary that the four sets of indices C₁⁺, C₁^-, C₂⁺, and C₂^- 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 y_i for each logical variable x_i and we introduce an inequality for each clause. The clauses can be satisfied simultaneously if and only if the inequalities can be satisfied simultaneously.

(a)

(5 points) Assume the four sets C₁⁺, C₁^-, C₂⁺, and C₂^- are distinct. Show that the inequality corresponding to (4) is implied by the inequalities corresponding to equations (2) and (3).

(b)

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

(c)

(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$.