Integer Programming Methods (2021/2022)

The vast majority of problems in combinatorial optimization can be formulated as an integer linear program (ILP): Maximize or minimize a linear objective function subject to linear constraints and the additional restriction that the decision variables can take only integer values (typically only 0/1). This makes ILPs a perfect tool for formulating problems in combinatorial optimization; many software packages are available for this. The drawback is that solving ILPs is generally a computationally demanding task; it is NP-hard. Nevertheless, in practice, also these problems have to be solved. In this part of the course we focus on techniques for solving ILPs.

Topics

  • Geometry of integer linear programs
  • Easy and difficult ILPs
  • Decomposition techniques
  • Power of additional variables
  • Geometric techniques based on cutting planes

Course Schedule

Lectures

Assignments

For more information on submission and grading see Intro slides.

Teachers

Remy Spliet
Erasmus University Rotterdam
spliet@ese.eur.nl

Matthias Walter
University of Twente
m.walter@utwente.nl

Literature

Conforti, Cornuéjols, and Zambelli. Integer programming.

Prerequisites

Linear algebra, linear programming, basic combinatorial optimization, basic complexity theory, basic programming