Course CO2b: Combinatorial Optimization 2b 

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: the interplay of polyhedra and lattices
- easy and difficult ILPs
- geometric techniques based on cutting planes
- algebraic techniques based on lattice basis reduction

Literature:
- B. Korte, J. Vygen, Combinatorial Optimization, Theory and Algorithms, Springer 2008 (available online via springerlink)
- A. Schrijver, Theory of Linear and Integer Programming, J. Wiley and Sons Ltd., Chichester, 1986.

Prerequisites:
- Knowledge of linear algebra.

Examination:
Take home problems.

Address of the lecturer:
Dr. F. Vallentin
Faculty of Electrical Engineering, Mathematics and Computer Science,
Delft University of Technology, Mekelweg 4, 2628 CD Delft
Phone: 015 - 2786262 E-mail: f.vallentin@tudelft.nl