Integer and Combinatorial Optimization
Spring 2019

Midterm Exam, Friday, March 29, 2019.

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       /20

Q5       /20

Total      /100
  1. (20 points) For each of the following feasibility problems, indicate if it is polynomially solvable or NP-complete. (No partial credit. 4 points per part, -1 point for incorrect answers.)
    1. Node packing with lower bound: Given a graph G = (V,E) and an integer k, does there exist a node packing of cardinality at least k?

      Polynomially solvable NP-complete

    2. Perfect matching: Given a graph G = (V,E), does there exist a perfect matching?

      Polynomially solvable NP-complete

    3. Minimum spanning tree with upper bound Given a graph G = (V,E), edge weights we for e E, and an integer W, does there exist a spanning tree with total weight no larger than W?

      Polynomially solvable NP-complete

    4. Traveling salesman problem with upper bound: Given a complete graph on vertices V , with integer edge weights we, and a positive integer W, does there exist a traveling salesman tour of length no more than W?

      Polynomially solvable NP-complete

    5. Binary knapsack problem with lower bound: Given a n, c n, and scalars b and z, does there exist a binary x n with aT x b and cT x z?

      Polynomially solvable NP-complete

  2. The binary variables x1,,x5 satisfy the constraints
    2xi + 2xj + 2xk ≤ 5  for 1 ≤ i < j < k ≤ 5.

    1. (4 points) Show the constraints
      xi + xj + xk ≤ 2  for 1 ≤ i < j < k ≤  5

      have Chvatal rank equal to one.

    2. (8 points) Show the valid constraint
      x1 + x2 + x3 + x4 + x5 ≤ 2

      has Chvatal rank no greater than 3.

    3. (8 points) Show the valid constraint
      x1 + x2 + x3 + x4 + x5 ≤ 2

      has Chvatal rank at least 2.

  3. Consider the problem
    max    4    ∑5    xj
    x∈ℝ       j=1
subject to  2xi + 2xj + 2xk ≤ 5  for 1 ≤ i < j < k ≤ 5

            xj binary for 1 ≤ j ≤ 5

    1. (10 points) Give the next level of the branch-and-bound tree using standard branch-and-bound. You need only give the optimal value at each node, together with the fathoming decision. Note that in an optimal solution to a relaxation, all the variables that take non binary values take the same value.

    2. (10 points) Give the tree you obtain if you use orbital branching. How many LP subproblems do you solve?
  4. (20 points)
    1. (8 points) The nonnegative integer variable y1 and the nonnegative continuous variable x must satisfy
x + y1 ≥ 43 .

      Give a valid linear constraint that is violated by the point x = 0, y = 41

    2. (12 points) Let y2 be a binary variable. Assume in addition that y1 and y2 must satisfy
      y1 + 3y2 ≤ 4.

      Lift the constraint you found in part 4a to give a valid constraint in x, y1, and y2.

  5. The wheel Wn is a graph G = (V,E) with n + 1 vertices labelled 0, 1,,n. It has 2n edges, of the form (1, 2), (2, 3), …, (n - 1,n), (1,n), and (0,i) for i = 1,,n. Our feasible region S consists of all incidence vectors of Hamiltonian cycles on Wn.

    Every feasible solution satisfies the n + 1 degree constraints

     xe = 2     for all v ∈ V.


    You may assume these equality constraints are linearly independent. (Hint: Let M be a square matrix with every entry equal to one. Let I be the identity matrix. You may assume that the columns of the matrix M - I are linearly independent.)

    1. (4 points) How many feasible solutions are there?
    2. (8 points) Show that the dimension of the feasible region is n - 1.
    3. (8 points) Show that the constraints xe 1 define facets of conv(S) for the edges (1, 2), (2, 3), …, (n - 1,n), (1,n).