COMP 567B           Integer Programming        Assignment 2

Due: Wed Feb 28,  2007   (in class or to Conor by 5pm)


1. Wolsey, P. 34 Ex. 2. Note line 5 should read "cover of the vertices by cliques."

2. Wolsey, P. 34 Problem 5 (i) and (ii).

3. (Wolsey p. 135, ex 5) Solve the following IP by the Gomory cutting plane procedure.
You should show each final LP dictionary, and how you generated each cut.
You can use any software you like to solve the LPs.

min 5 x1 + 9 x2 + 23 x3
          
s.t.    20 x1 + 35 x2 + 95 x3 >= 319

x1, x2, x3 non-negative integers.

4. (Wolsey p.135, ex 6) Solve the following problem using MIR inequalities:


max 5 x1 + 9 x2 + 23 x3 - 4 s
          
s.t.    2 x1 + 3 x2 + 9 x3 <= 32 + s

x1, x2, x3 non-negative integers.
s >= 0, real valued.