MATP6620 / ISYE6760 Combinatorial Optimization and Integer Programming
Homework 5.

Due: Friday, April 8, 2011.
Penalty for late homeworks: 10% for each day or part of a day.

  1. Consider the 0-1 equality knapsack problem
    n+1 max {- xn+1 : 2x1 + 2x2 + ...+ 2xn + xn+1 = n,x ∈ B },

    where n is an odd integer. We wish to solve this problem using a branch and bound algorithm with linear programming relaxations. Assume we always branch using variable dichotomies (ie, add the constraints xi = 0 or xi = 1 for some i). Show that an exponential number of nodes of the branch and bound tree must be considered to solve the problem.

  2. In Question 1, what is the Gomory cutting plane at the root node, and what would happen if we applied that?
  3. Use branch-and-bound with LP relaxations to solve the knapsack problem
    max 20x + 30x + 40x + 42x s.t. x1 + 3x2 + 5x 3 + 6x4 ≤ 7 1 2x binary f3or i = 1,..4.,4, i

    branching using variable dichotomies. Give a valid cover inequality violated by your solution to the root node. What do you get if you lift this inequality?

  4. In the examples below, x is required to be a nonnegative vector in IR3 and y is constrained to be a binary vector with three components. A set of constraints that must be satisfied by x and y is given, and a point that satisfies these constraints is also given. Find a valid flow cover inequality that cuts off this point.
    1. Constraints:
      x1 + x2 + x3 ≤ 7, x1 ≤ 3y1, x2 ≤ 5y2, x3 ≤ 6y3.

      Point:

      2 x = (2,5,0), y = (-,1,0). 3

    2. Constraints:
      7 ≤ x1 + x2 + x3, x1 ≤ 3y1, x2 ≤ 5y2, x3 ≤ 6y3.

      Point:

      2 x = (2,5,0), y = (3,1,0).

  5. Given a graph G = (V,E) with n vertices, define the convex set
    ∑m CG := {X ∈ IRn ×n : Xij = 0 ∀(i,j) ∈ E, X = ykyTk for some yk ∈ IRn+, trace(X) = 1}. k=1

    How are extreme points of CG related to node packings in G? Can you formulate the node packing problem using CG?

  6. Give a progress report on your project. Your report should be at least a couple of paragraphs long. It doesn’t need to repeat anything from your initial report from March 4.
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday, Wednesday, 2-3pm.