Combinatorial optimization and polyhedra

Objective: Many problems arising from various domains can be formulated as combinatorial optimization problems. The resolution of these problems consists in maximizing or minimizing an objective function over a polyhedron. This course is meant to be an introduction to polyhedral analysis for combinatorial optimization problems. We present the main elements of such an analysis and study the algorithmic consequences for the resolution of the underlying problems. In order to illustrate these approaches, some real applications will be given.

Contents:

  • Combinatorial optimization and polyhedra

  • Dimension, facets of polyhedra

  • Minimal description of a polyhedron by a system of linear inequalities

  • Polyhedral approach

  • Combinatorial polyhedral and min-max relations

  • Applications

Bibliography

  • W. Cook, W. Cunningham, W.R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", Wiley (1998).

  • A. R. Mahjoub, "Approches polyédrales", dans "Optimisation Combinatoire 1: Concepts fondamentaux", V. Paschos (Ed.), Hermes (2005) pp. 263-329.

  • G. L. Nemhauser and L. A. Wolsey, "Integer and Combinatorial Optimization", Wiley (1988).