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:

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.