Name:

MATP6620/DSES6770
Combinatorial Optimization and Integer Programming
Spring 2003

Final Exam, Tuesday, May 6, 2003.

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 three hours.

Q1			/20
Q2			/20
Q3			/25
Q4			/15
Q5			/20
Total			/100

1.

(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. You may also want to look at the node packing problem:

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

(intentionally left blank)

2.

(20 points, each part is worth five points)
Consider the 0-1 equality knapsack problem

$$\min \{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)

Show that x_n+1=1 in any feasible solution to (KE). What is the optimal value of (KE)?

(b)

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)

Derive the valid inequality

$$x_1 + x_2 + \ldots + x_n \leq \lfloor n/2 \rfloor$$

using the Chvatal-Gomory rounding procedure.

(d)

What is the minimum number of nodes we need in the branch and bound process 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.)

(intentionally left blank)

3.

(25 points; each part is worth 5 points)
We have n objects and we want to find an ordering of the objects, so, given two objects i and j, either i is before j or j is before i. The ordering should be consistent; that is, if i is before j and j is before k then i should be before k. We get a reward w_ij if i is before j and a reward w_ji if j is before i. The objective is to maximize

$$\begin{array}{cc} \sum & w_{ij}. \\ \mbox{all pairs $i$ , $j$ ,} & \\ \mbox{$i$\space before $j$ } \end{array}$$

We can model this as an integer programming problem by introducing variables x_ij defined as follows:

$$x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if $i$\space is before $j$ } \\ 0 & \mbox{otherwise} \end{array} \right.$$

Let S be the set of points x which correspond to orderings; let conv(S) be the convex hull of S. This formulation has n(n-1) variables. You may assume that the dimension of conv(S) is n(n-1)/2.

(a)

Show that x_ij+x_ji=1 is valid for every ordering.  

(b)

Show that the inequality $x_{ij}+x_{jk}+x_{ki}\leq 2$ is valid for S for any i, j, and k.  

(c)

For this part only, let n=3. Show that $x_{12}+x_{23}+x_{31}\leq 2$ is a facet of conv(S).

(d)

Let $U=\{u_1,\ldots,u_k\}$ and $W=\{w_1,\ldots,w_k\}$ be two subsets of the objects. Show that the inequality

$$\sum_{u_i \in U, w_j \in W, i \neq j} x_{w_j,u_i} + \sum_{i=1}^k x_{u_i,w_i} \leq k^2-k+1$$

is valid for S. (Note that the inequality includes k edges pointing up in the picture and k(k-1)=k²-k edges pointing down.)  

(e)

Find a point $\bar{x}$, $0\leq \bar{x}_i \leq 1$, which satisfies all the equalities in part 3a and all the inequalities in part 3b, but which violates the inequality in part 3d. (Hint: such a point exists when k=3.)

(intentionally left blank)

(intentionally left blank)

4.

(15 points; each part is worth 5 points)
Consider the integer programming problem

$$\begin{array}{lrcrcrcrcrcl} \min & -x_1 & + & 2x_2 & + & 3... ...&&&&& x & \geq & 0, & \mbox{and} & \mbox{integer} \end{array}$$

One feasible integral solution is x=(0,1,1,0,0), which has value 5. The linear programming relaxation of this problem is obtained by ignoring the condition that the variables x should be integral. The optimal tableau for the LP relaxation is

$$\begin{tabular}{\vert rrrrr\vert r\vert} \hline 2 & 1 & 0.5 ... ...& 0 & 3.5 \\ 1 & 3 & 2.5 & 0 & 1 & 5.5 \\ \hline \end{tabular}$$

(a)

What is the dual problem to the LP relaxation?

(b)

Show that any feasible solution to the LP relaxation with $x_1 \geq 1$ has value at least 5.5.

(c)

What can you say about the value of x₁ in any optimal solution?

(intentionally left blank)

5.

(20 points)
When we looked at tabu search, we considered the problem of finding the minimum spanning tree in a graph subject to some side constraints. The tabu search process gives a feasible solution, and hence an upper bound on the optimal value. How would you find a lower bound on the optimal value? (Note: please include details. You will not get much credit for a two-word answer!)

(intentionally left blank)