67.612 Combinatorial Optimization and Integer Programming, Spring 93.

Midterm Exam, Monday, March 29, 1993.

Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts. You may use one sheet of handwritten notes. The exam lasts two hours.

1.

(20 points) Find the shortest path from vertex 1 to vertex 6 in the following graph. Edge lengths are indicated on the edges.

2.

(20 points) For each of the following graphs, find the maximum cardinality matching and give a short proof that it realy does contain the largest possible number of edges.

3.

(40 points)

(a)

(35 points; each part is worth five points.)  Consider the binary knapsack problem:

$$\begin{array}{lrcrcrcrcrcl} \max & 10x_1 & + & 8x_2 & + & ... ... \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\{10x_1+8x_2+5x_3+2x_4+x_5 : x \in P \}$.

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)

(5 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}$$

Generalize the results of part 3a to give a class of valid inequalities for this problem.

4.

(20 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 want to look at the complement of G=(V,E), that is, the graph G=(V,E') where e is in E' if and only if it is not in E.)