67.612/92.672
Combinatorial Optimization and Integer Programming
Spring 97

Midterm Exam, Wednesday, April 9, 1997.

Please do all three 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.

1.

(25 points) The max clique feasibility problem can be described as follows:

An instance consists of a graph G=(V,E) and an integer k. The answer is YES if the graph contains a clique with at least k vertices; otherwise, the answer is NO.

Show that the max clique problem is NP-complete. (Hint: You may assume the following problems are NP-complete: SATISFIABILITY, 3-SATISFIABILITY, NODE PACKING, HAMILTONIAN PATH, HAMILTONIAN CIRCUIT. It should be possible to use one of these in a reduction. Instances of these problems are defined as follows:

SATISFIABILITY: Given a set of boolean variables and a set of clauses consisting of literals (each of which is a variable or a negated variable) does there exist an assignment for the variables so that at least one literal in each clause is true?
3-SATISFIABILITY: An instance of satisfiability where each clause contains exactly three literals.
NODE PACKING: Given a graph G=(V,E) and a integer k, does there exist a subset $U \subseteq V$ with $\mid \! U \! \mid = k$ where no two of the vertices in U share an edge?
HAMILTONIAN PATH: Given a graph G=(V,E), does there exist a path which visits every vertex?
HAMILTONIAN CIRCUIT: Given a graph G=(V,E), does there exist a circuit which visits every vertex?)

2.

(50 points)

(a)

(42 points; each part is worth six points.)  Consider the binary knapsack problem:

$$\begin{array}{lccrcrcrcrcrcl} \max & z & := & 10x_1 & + & ... ... \qquad (KP) \\ &&&&&&&&& x_i && \mbox{binary.} \end{array}$$

Let $P=\{x \in {\Re}^5_+:2x_1+4x_2+5x_3+3x_4+4x_5\leq 10, 0 \leq x_i \leq 1\}$ and  $S=P\cap{\cal Z}^5$.

i.

Solve the LP-relaxation $\max\{z : x \in P \}$. (Hint: You can solve the relaxation by ordering the variables in decreasing order of c_j/a_j and then successively using as much as possible of the next available variable until all of the resource b is consumed. Here, c_j are the objective function coefficients, a_j are the constraint coefficients, and b is the right hand side of the constraint.)

ii.

What is the dimension of S?

iii.

Prove that $x_1+x_2+x_3 \leq 2$ is a valid inequality for S.

iv.

Prove that $x_1+x_2+x_3 \leq 2$ is a facet of conv(S), the convex hull of S.

v.

What is the Chvatal-Gomory rank of the inequality $x_1+x_2+x_3 \leq 2$?

vi.

Prove that $x_3+x_4+x_5 \leq 2$ is a valid inequality for S.

vii.

Show that the inequality $x_3+x_4+x_5 \leq 2$ can be lifted to give a stronger valid inequality for S.

(b)

(8 points) Consider the general binary knapsack problem:

$$\begin{array}{lrcl} \max & \sum_{i=1}^n c_ix_i \\ \mbox{... ...^n a_ix_i & \leq & b \\ & x_i && \mbox{binary,} \end{array}$$

where b>0, and a_i>0, c_i>0 for $i=1,\ldots,n$. Generalize the results of part 2a to give a class of valid inequalities for this problem.

3.

(25 points) Consider the 0-1 equality knapsack problem

$$\max \{-x_{n+1} : 2x_1 + 2x_2 + \ldots + 2x_n + x_{n+1} = n, x \in B^n \}, \qquad\qquad (KE)$$

where n is an odd integer. We wish to solve this problem using a branch and bound algorithm with linear programming relaxations.

(a)

(5 points) Show that x_n+1=1 in any feasible solution to (KE).

(b)

(10 points) Assume we always separate using variable dichotomies (ie, add the constraints x_i = 0 or x_i = 1 for some i). Show that if no more than $\lfloor n/2 \rfloor$ of the variables $x_1,\ldots,x_n$ have been fixed at 0 or 1 then the relaxation has value 0. Hence show that an exponential number of nodes of the branch and bound tree must be considered to solve the problem.

(c)

(10 points) What is the minimum number of nodes we need if we can separate using any linear inequality? (Assume that you obtain an extreme point optimal solution to any relaxation that you set up, provided such a solution exists.)