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.


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

Course Schedule



For more information on submission and grading see Intro slides.


Remy Spliet
Erasmus University Rotterdam

Matthias Walter
University of Twente


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


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