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:

Let and .- i.
- Solve the LP-relaxation .
- ii.
- What is the dimension of
*S*? - iii.
- Prove that
is a valid inequality for
*S*. - iv.
- Prove that
is a facet of conv(
*S*), the convex hull of*S*. - v.
- What is the Chvatal-Gomory rank of the inequality ?
- vi.
- Prove that
is a valid inequality for
*S*. - vii.
- Show that the inequality
can be lifted
to give a stronger valid inequality for
*S*.

- (b)
- (5 points)
Consider the general binary knapsack problem:

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

Show that the*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*.*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*.)

John E. Mitchell