Combinatorial Optimization and Integer Programming
Spring 2011

Midterm Exam, Tuesday, April 19, 2011.

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, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

Q1       /20

Q2       /20

Q3       /20

Q4       /40

Total      /100
  1. (20 points; each part is worth 10 points)
    1. The binary variables x1, x2, x3, and x4 must satisfy the constraint
      6x1 + 7x2 + 4x3 + 5x4  ≤ 13.

      Find a minimal cover inequality. Lift the cover inequality.

    2. The binary variables z1, z2, z3, and z4 must satisfy the constraint
      6z1 + 7z2 - 4z3 + 5z4 ≤ 9.

      Use the results of part (a) to derive an inequality that defines a facet of the set of z ∈ IB4 satisfying the constraint. Why is your constraint facet-defining?

  2. (20 points)

    The linearly dependent vectors x1,,xm in IRn are all on the hyperplane aT x = b, where b0. Show that they are affinely dependent.

  3. (20 points)

    Let G = (V,E) be a graph with nonnegative edge weights we.

    1. (15 points) Show that the problem of finding the maximum weight matching on G is equivalent to finding a maximum weight perfect matching on another graph G= (V ,E) with nonnegative edge weights we, where V and Eare obtained from V and E by adding certain vertices and edges.
    2. (5 points) Given a maximum weight perfect matching problem, how can you construct an equivalent minimum weight perfect matching problem with nonnegative edge weights?
  4. (40 points; 6 parts on 3 pages)

    This question is concerned with node packings in the following graph.

    1. (5 points) The set of feasible solutions to the node packing problem on a graph G = (V,E) with n vertices and m edges can be written as
      S :=  {x ∈ IBn  : xu + xv ≤ 1 ∀ (u,v) ∈ E }.

      We saw in class that the convex hull of S has dimension n and the nonnegativity constraints define facets of conv(S). Give another facet of conv(S) for the given graph.

    2. (5 points) Find a packing of cardinality 4 in the given graph.
    3. (10 points) Give a set of valid inequalities that together show that there cannot be a packing of cardinality greater than 4.
    4. (5 points) Is the graph perfect? (Justify your answer.)
    5. (7 points) Find nonnegative integral node weights cv such that the optimal value of the LP relaxation
      max        ∑     c x
             v∈V  v v
subject to     xu + xv  ≤   1  ∀(u,v) ∈ E
              0 ≤  xu  ≤   1  ∀v ∈ V

      is not integral.

    6. (8 points) The Lovasz Θ semidefinite programming relaxation of the node packing problem has dual problem
      min                  z
subject to  - Sii +  z           =  1  i = 1,...,n       (D )
           - Sij         +  yij  =  1  if (i,j) ∈ E
           - Sij                 =  1  if (i,j) ⁄∈ E
              S                  ≽  0

      Give a feasible solution to the dual problem with value 4.