Course Description
This course is primarily intended for PhD students who want to pursue integer programming as a possible dissertation area. This course builds on IE 716: Integer Programming–Theory and Computatations.
Course Contents
1. Lenstra’s algorithm. Lattices and bases for lattices, unimodular transformations, shortest vector problems, reduced basis of a lattice, Hermite normal form and the solution to linear diophantine equations, the LLL algorithm for basis reduction, Lenstra’s algorithm for integer programming.
2. Modern approaches to cutting planes for integer programs. Maximal lattice-free convex sets of vector spaces, Minkowski functionals of convex sets, corner polyhedra and intersection cuts, cutting planes from multiple rows of the simplex tableau. The lattice-free closure of a rational polyhedron, and finite convergence to the integer hull.
3. Symmetry in Integer Programming. Detecting and breaking symmetries, branching rules to deal with symmetry, structure of the permutahedron.
4. Extended formulations. Extended formulations and the extension complexity of polytopes, the slack matrix and its positive rank, extension complexities of various combinatorial problems.
5. Duality in Integer Programming. Various dual approaches to obtaining lower bounds for inte- ger programs: subadditive duality, Lasserre’s duality, and extensions to convex integer programming problems.
Textbooks/References
There is no single textbook for this course. Material covered here can be found in some of the books/papers listed below.
1. M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics 2, Springer-Verlag, 1988.
2. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.
3. C. Lekkerkerker and P. Gruber, Geometry of Numbers, North-Holland, 1987.
4. D. Bertsimas and R. Weismantel, Optimization Over Integers, Dynamic Ideas, 2005.
5. J. De Loera, R. Hemmecke, and M. K ̈oppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS-SIAM Series on Optimization, 2012.
6. Several recent and relevant research and survey papers.