Skip to main content

IE 607: Polyhedra and Combinatorial Optimization

Prerequisite: IE 601

Course Content

  1. Elements of Polyhedral Theory. Introduction to polyhedra, faces and the face-lattice, size issues such as facet and vertex complexity. Polarity and the equivalence of (strong/weak) optimization and (strong/weak) separation for polyhedra.

  2. Properties of Integral Polyhedra. Total Dual Integrality (TDI), Box TDI, Hilbert Bases and minimal TDI systems, behaviour of TDI systems under transformations, integer versions of Carathéodory’s Theorem, recognizing integrality. Size estimates: facet and vertex complexity, number of extreme points.

  3. Unimodularity and Total Unimodularity. Total unimodularity and integral polyhedra, exact characterization of unimodular matrices, balanced matrices.

  4. Matching Polyhedra. Polytopes related to bipartite and nonbipartite matching problems, exact description, separation, and other properties.

  5. Perfect Graph Theorems and Polyhedral Implications. The perfect graph theorem, relations between integral polyhedra and perfect graphs, the Lovász; body and polynomial solvability.

  6. Polymatroids and Greedy Algorithms. Matroids and polymatroids and related polytopes. Optimization over matroid polytopes and the greedy algorithm. Connections with submodular function minimization.

  7. Extended Formulations for Combinatorial Optimization problems. Extension complexity of polytopes and Yannakakis's result, symmetric vs nonsymmetric extended formulations, extension complexity of the Traveling Salesman and the Matching polytopes. Locally ideal extended formulations.

Texts/References

  • A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.

  • A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (Volumes A, B, and C), Springer, 2003.

  • M. Grotschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1993.

  • J. De Loera, R. Hemmecke, and  M. K ̈oppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MPS-SIAM Series on Optimization, SIAM, 2013.

  • G. M. Ziegler, Lectures on Polytopes, Springer, 1998.

  • W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, Wiley-Interscience, 1997.