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.

2. Lecture 2 (03/18/2010): LLL basis reduction algorithm, Lenstra's algorithm for IP in fixed dimensions.

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.

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.

5. Lecture 5 (03/30/2010): Comparison of Split closure, Triangle Closure and Quadrilateral Closures for two rwo cutting planes, Lifting Integer Variables.

6. Lecture 6 (04/01/2010): Characterizing regions for ``optimal lifting''. Unique Minimal Liftings.

7. Lecture 7 (04/06/2010): Bender's Reformulation and Cuts.

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.

(More lectures will be posted soon !)

Homework 1 (due date : 03/30/2010)

Homework 2 (due date : 04/13/2010)