45-831 : Advanced Integer Programming (Spring 2010)
Time and Location : Tue-Thurs, 10:30 - 12:20. Room 147, Posner Hall.
This course covers advanced techniques and recent research directions in Integer Programming. The course aims to cover the following topics :
1. Lecture 1 (03/16/2010): Relevant aspects of the theory of lattices. Lecture given by Amitabh Basu.
2. Lecture 2 (03/18/2010): LLL basis reduction algorithm, Lenstra's algorithm for IP in fixed dimensions. Lecture given by Amitabh Basu.
3. Lecture 3 (03/23/2010): Maximal lattice-free convex sets, Minkowski functionals of convex sets, Corner Polyhedra and Intersection cuts, Cutting planes from multiple rows of the simplex tableau. Lecture given by Amitabh Basu.
4. Lecture 4 (03/25/2010): Maximal S-free convex sets and cutting planes with non-negativity constraints on basic variables, Cutting planes from two rows, structure of MLFC sets in 2 dimensions, Facet theorem for two row cuts. Lecture given by Amitabh Basu.
5. Lecture 5 (03/30/2010): Comparison of Split closure, Triangle Closure and Quadrilateral Closures for two rwo cutting planes, Lifting Integer Variables. Lecture given by Amitabh Basu.
6. Lecture 6 (04/01/2010): Characterizing regions for ``optimal lifting''. Unique Minimal Liftings. Lecture given by Amitabh Basu.
7. Lecture 7 (04/06/2010): Bender's Reformulation and Cuts. Lecture given by Gerard Cornuejols.
8. Lecture 8 (04/08/2010): Dealing with integral non-basics directly - Infinite Group Problem, Minimal Functions/Inequalities, Facets and Extreme Inequalities, Facet theorem, Interval Lemma, Gomory-Johnson's 2-slope Facet Theorem.
Lecture given by Amitabh Basu.
(More lectures will be posted soon !)
Homework 1 (due date : 03/30/2010)
Homework 2 (due date : 04/13/2010)