Doel vak

A student who successfully completes the course will have an
understanding of the techniques of combinatorial optimization and
integer programming, and be ready to apply them to problems encountered
in practice.

Inhoud vak

* The notion of efficiency in algorithms; distinguishing between
tractable and computationally "hard" problems.
* The correctness and efficiency of key algorithms in combinatorial
optimization will be shown rigorously. Problems studied will include:
minimum spanning tree, maximum flow, minimum cost flow, and matching.
* Formulation of problems as integer programs; the notion of the
strength of a formulation; the central role of integral formulations.
* The main techniques and theory used in commercial integer programming
solvers such as CPLEX and Gurobi will be investigated in detail. A main
focus will be on the powerful cutting-plane method.
* Column generation, Lagrangian relaxation, modelling of disjunctions,
and other problem-tailored techniques will be discussed.
* Experience in the use of integer programming solvers will be gained.

Onderwijsvorm

4 hours per week of lectures, 2 hours per week discussing theoretical
exercises, and 2 hours per week working on problems with the aid of
software tools in a computer lab.

Toetsvorm

Theory assignments - group assessment
Programming assignments - group assessment
Final exam – individual assessment

Vereiste voorkennis

Linear Algebra
Operations Research I

Literatuur

Main book: Cook, Cunningham, Pulleyblank & Schrijver, Combinatorial
Optimization (1997)
Additional reference: Conforti, Cornuejols & Zambelli, Integer
Programming (2014)
NB: Electronic access to both books is available through the library.

Overige informatie

The course is suitable to be taken in an exchange program.

Aanbevolen voorkennis

It is expected that students are familiar with the contents of
Operations Research I - and in particular linear programming - at the
start of the course.

Some amount of programming experience, while not required, is helpful.