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.

   Solution:

   The model is

   

   For the final constraint for condition (e), we need

   

   or equivalently, we need

   

   The corresponding disjunctive cut is

   

   from taking the larger coefficient for each x_i. We can confirm the constraint is equivalent to the required logical condition by examining cases.

   An alternative approach for constraint (e): this is the more standard approach, and doesn’t need to exploit the disjunctive cut structure. We introduce a new binary variable z_e and impose two constraints:

   
   This works since we have two cases:
   • If z_e = 1 then we must choose at least one of investments 1,2,3. There is no restriction imposed on investments 2,5,6,7.
   • If z_e = 0 then we must choose at least two of investments 2,5,6,7. There is no restriction imposed on investments 1,2,3.
2. 1. (15 points) We have a collection of 2k - 1 objects, where k is a positive integer. Let

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

      

      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,

      Show that the clique constraint

      

      has Chvatal rank at most 4.

   Solution:

   1. For each subset K with |K| = k, we have the valid constraint

      Adding the inequalities, we get

      

      where the term on the right hand side is the number of subsets of cardinality k and the term on the left is the number containing any particular x_i. Dividing by the term on the left and rounding, we get

      
      as required. Thus, the given inequality has Chvatal rank at most 1.

      An alternative approach, which uses only a linear number of subsets:

      Consider the following 2k - 1 subsets of the items, each of cardinality k:

      
      Each item appears in exactly k of these subsets. The sum of the given valid inequalities for these subsets can be written

      Dividing by k and rounding down gives the valid inequality

      

      so the required inequality indeed has Chvatal rank no larger than one.

   2. From part 2a, we get:
      • clique inequalities for subcliques of size 3 have Chvatal rank at most 1.
      • clique inequalities for subcliques of size 5 have Chvatal rank at most 2.
      • clique inequalities for subcliques of size 9 have Chvatal rank at most 3.
      • clique inequality for the clique of size 17 has Chvatal rank at most 4.
3. An integer program of the form

   has an LP relaxation which has optimal form

   

   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 x₁ or x₃ in an optimal integer solution?
   2. (10 points) What are the Gomory cutting planes corresponding to the two constraints?

   Solution:

   1. If x₁ ≥ 1 then the objective function value is at least 10.4. So we must have x₁ = 0 in any optimal solution.

      If x₃ ≥ 5 then the objective function value is at least 10.7. So we must have x₃ ≤ 4 in any optimal solution.

   2. The cuts are
      
4. 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.

   Solution

   1. Using a greedy algorithm gives one optimal solution with value 42:

      

   2. 1. A feasible solution to the relaxation with value 36, where all nonzero x_e are equal to one:

         

         The solution uses 10 edges and has at least one edge incident to each vertex.

         There is a better feasible solution to the relaxation: replace edges (d,h) and (d,j) by edges (g,p) and (h,j), which has value 35.

      2. A spanning tree is acyclic and connected. The feasible solution above is neither. Violated valid constraints include
         
      3. The optimization problem of finding the minimum spanning tree can be solved in polynomial time. From the polynomial equivalence of separation and optimization, this means the separation problem can also be solved in polynomial time.