Course IntPM: Integer Programming Methods

Time:	Monday 11.00 - 12.45 (November 18 – December 16 and January 20 – February 17).
Location:	Hans Freudenthalgebouw, Room 611AB, Budapestlaan, Utrecht (De Uithof).
Lecturer:	Dr. R. Spliet (Erasmus University Rotterdam), Dr. M. Walter (University of Twente)

Course description:
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. The following topics will be treated:
- the expressive power of ILPs in combinatorial optimization
- geometry of integer linear programs
- easy and difficult ILPs
- geometric techniques based on cutting planes
- decomposition techniques

More information can be found on this website.

Literature:
- Conforti, Cornuejols, and Zambelli, Integer programming, Springer 2014 (available online via springerlink)

Prerequisites:
- Knowledge of linear algebra and linear programming.

Examination:
Take home problems.

Address of the lecturer:
Dr. Remy Spliet
Erasmus Universiteit Rotterdam, Department of Economics
Postbus 1738, 3000 DR Rotterdam
Phone: 010 4081342
E-mail: spliet@ese.eur.nl,

Dr. Matthias Walter
University of Twente, Faculty of Electrical Engineering, Mathematics & Computer Science
P.O. Box 217, 7500 AE Enschede
Phone: 053 4898744
E-mail: m.walter@utwente.nl,