Combinatorial Optimization and Integer Programming
Spring 2009

Midterm Exam, Thursday, March 19, 2009.

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 110 minutes.

Q1       /20

Q2       /30

Q3       /20

Q4       /20

Q5       /10

Total      /100
  1. (20 points)
    Recall the following material on clustering problems from Homework 4:

    Given the complete graph Kn =: (V,E) on n vertices, a clustering of the vertices is obtained by choosing an integer p and a partition of the vertices into p sets V 1,,V p satisfying:

    V s V t = for 1 s < t p and s=1pV s = V .

    Note that p is not fixed. The incidence vector of this clustering is defined by

        1   if i and j are in the same set Vs
xij =   0   otherwise.

    Let Q be the set of incidence vectors of clusterings for Kn. Let edge (i,j) have weight wij. The clustering problem for this set of edge weights is then

                     ∑n -1∑n
max         z :=    i=1   j=i+1wijxij
subject to  x is the incidence vector of a clustering

    The edge weights wij can be positive or negative. Valid triangle inequalities for this problem for three distinct vertices i, j, k are

    xij + xjk - xik ≤ 1.

    Let U V and let p = |U|. Assume p 5 and p is odd. Let E(U) be the edges with both endpoints in U. Let C E(U) be a Hamiltonian tour through the vertices U. Denote the order of the vertices in the tour as i1 -i2 --ip -i1. Prove that the following constraint is valid for the clustering problem:

    ∑           ∑          p --1-
   xe -          xe ≤    2  .
e∈C      e∈E(U)\C

  2. (30 points)
    Solve the following binary knapsack problem using branch-and-bound:
    max        35x    +  27x    +  15x    +  8x
               1         2         3        4
subject to 10x1   +   9x2   +   6x3   +  4x4  ≤   16
                                x1, x2, x3, x4    binary.

    (Note: Linear programming relaxations of knapsack problems can be solved very easily. In particular, here the variables are ordered so that the ratios of the objective function coefficients ci to constraint coefficients ai satisfy

    c1- ≥  c2-≥  c3-≥  c4-.
a1     a2    a3    a4

    Then the solution is to take x1 as large as possible, then x2 as large as possible, then x3 as large as possible, and then x4 as large as possible. For the initial LP relaxation, this gives a solution of x = (1,23, 0, 0).

    It may be useful to know that 0.7 × 35 = 24.5.)

  3. (20 points)
    The binary variables xi, i = 1,, 4 satisfy
    x   +   x   +        x           ≤   2
  1      2             3
x1          +   (1 - x3)  +  x4  ≤   2

    The constraint x2 + x4 2 follows trivially from the upper bounds on the binary variables. By thinking of this as a constraint when x1 = 0, lift it to give a stronger valid constraint of the form

    αx1 +  x2 +  x4 ≤  2.

  4. (20 points)
    We want to solve the Max Cut problem on the graph G = (V,E) which has edge weights we. Part of the graph has the following structure:


    Prove that the valid inequality

    xab + xbd + xdf - xfh - xgh - xeg - xce - xac ≤ 2

    does not define a facet of the convex hull of the set of incidence vectors of cuts.

  5. (10 points)
    Let c and a be integral positive n-vectors and let b be a positive integer. The knapsack problem max{cT x : aT x b, x ∈ IBn} can be solved in time polynomial in n and b, yet the knapsack problem is NP-Hard. Why is this not a contradiction?