Combinatorial Optimization


Course Objective

In this course you will learn how to develop efficient algorithms for
solving fundamental optimization problems in operations research.
The objectives of the course are to:
- learn about fundamental optimization problems (Scheduling, vehicle
routing, facility location, network design, ...)
- learn algorithms for solving these problems
- learn to prove performance guarantees (running time, approximation
- apply the theory by implementing some of these algorithms.
- construct and implement (in Python) your own algorithms for
optimization problems.

Course Content

Topics that will be covered in the course are:
- Scheduling problems, routing problems, facility location problems.
- Integer linear programming, dynamic programming, local search
algorithm, randomized algorithms.
- Theoretical performance guarantees: approximation ratio, polynomial
running time.
- Computational complexity theory and hardness of approximation.
- Algorithms for optimization problems in general.

Teaching Methods

Lectures (4hours) and tutorials (2hours). Attendance is not compulsory.

Method of Assessment

The final grade is determined by a written exam (60%) and group
assignments (40%). In the assignment you will apply the theory and
implement algorithms for optimization problems. We use Python for this.

Entry Requirements

Basic knowledge of graph theory and linear programming. Basic
programming skills, preferably Python. If you have experience with other
languages (java, R, Matlab, ...) then Python will be easy to learn.


We use the following book which is freely available for download.
Lecture notes covering the relevant chapters are available on Canvas.
- D.P. Williamson and D.B. Shmoys, The Design of Approximation
Algorithms, Cambridge University Press, 2011.
Part of the course is based on additional material which
will be provided through Canvas.

Target Audience

Anyone with sufficient pre-knowledge and an interest in algorithms for
combinatorial optimization problems in Operations Research.

Recommended background knowledge

Basic knowledge on graph theory, linear programming, and combinatorial
optimization is assumed. For example, the bachelor courses Operations
Research 3 (SBE) and Combinatorial Optimization for FEW (X_401067) each
provide sufficient pre-knowledge.

General Information

Course Code E_EORM_COPT
Credits 6 EC
Period P1
Course Level 400
Language of Tuition English
Faculty School of Business and Economics
Course Coordinator dr. ir. R.A. Sitters
Examiner dr. ir. R.A. Sitters
Teaching Staff dr. ir. R.A. Sitters

Practical Information

You need to register for this course yourself

Last-minute registration is available for this course.

Teaching Methods Seminar, Lecture, Computer lab
Target audiences

This course is also available as: