MATP6620/ISYE6770
Combinatorial Optimization and Integer Programming
Spring 2017

Midterm Exam, Friday, March 31, 2017.

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.

  1. (20 points) You wish to choose from a set of possible investments {1,…, 7}, subject to the following constraints:
    1. You cannot invest in all of them.
    2. Investment 1 must be chosen if investment 3 is chosen.
    3. Investment 5 can be chosen only if investment 2 is also chosen.
    4. You must choose either both investments 1 and 6 or neither.
    5. You must choose either at least one of the investments 1,2,3, and/or at least two investments from 2,5,6,7.

    Model this as a 0-1 integer programming feasibility problem.

    1. (15 points) We have a collection of 2k - 1 objects, where k is a positive integer. Let
      { 1 if object i selected xi = 0 otherwise

      Assume that at most one item can be selected from each subset of size k. Show that the constraint

      2∑k-1 xi ≤ 1 i=1

      has Chvatal rank at most one.

    2. (10 points) In a particular node packing problem on a graph G = (V,E), we have a clique C of size 17. The initial LP relaxation only includes constraints for the edges,
      xi + xj ≤ 1 for all edges (i,j) ∈ E.

      Show that the clique constraint

      ∑ x ≤ 1 i i∈C

      has Chvatal rank at most 4.

  3. An integer program of the form
    minx cTx subject to Ax = b x ≥ 0, integer

    has an LP relaxation which has optimal form

    min 3.2x + 0.7x + 7.2 1 3 subject to 2.1x1 + x2 + 1.3x3 = 5.2 1.3x1 - 0.6x3 + x4 = 2.6 xi ≥ 0 ∀i

    with optimal basic feasible solution x = (0, 5.2, 0, 2.6) with value 7.2.

    1. (10 points) Assume we know a feasible integer solution with value 10. Does this tell us anything about the nonbasic variables x1 or x3 in an optimal integer solution?
    2. (10 points) What are the Gomory cutting planes corresponding to the two constraints?
    1. (10 points) Solve the minimum spanning tree problem on the following graph:

    2. We could imagine a cutting plane approach to solve the minimum spanning tree problem, initializing with the constraints that every vertex is adjacent to at least one edge in the solution, and the total number of edges is one less than the number of vertices.
      1. (10 points) Show that such a relaxation for the graph above has a feasible solution with value 36.
      2. (10 points) Can you find valid constraints that are violated by your solution in part 4(b)i?
      3. (5 points) Consider now a general graph. Let S denote the set of incidence vectors of spanning trees. Given a feasible solution x to a relaxation of the minimum spanning tree with x ⁄∈ conv(S), a separation routine can be designed to find a violated valid constraint for conv(S). In the best case, would you expect such a routine to run in polynomial time? Justify your answer.