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.