### COMP 567B
Discrete Optimization-II Assignment 2

** Due: Wednesday, March 3, 2010 (in class)**

Midterm will be held March 17 (in class)

Problems from Integer Programming, Wolsey

1. (Unimodular Matrices) P. 50, Ex. 3.

2. (Branch and Bound) P. 109, Ex. 4. You may use LP-solve or
CPLEX to solve the LP subproblems.

Show the branch and bound tree, and the LP solution for each
subproblem (eg. cut and paste solution from the LP solver)

3. (Cutting Planes) Solve P.109, Ex. 4 using Gomory's
cutting plane algorithm as given in Section 8.6.

To do this you need access to the optimal dictionary for each LP
problem solved.

A way to do this in maple is shown here:

http://cgm.cs.mcgill.ca/~avis/courses/567/maple/gomory_out

Show the LP dictionary for each LP solved, and show by hand
how you derive each cutting plane.

Note: You may stop after 3 complete iterations of Gomory's
algorithm if you do not find an integer solution.

Ie. you should generate at least 3 cutting planes and solve each new LP
obtained.