Course ObjectiveIn this course you will learn about the theory of combinatorial
optimization problems. Also, you will apply the theory to model and
solve complex problems using the available software.
In particular, we consider performance measures for algorithms for
combinatorial problems such as the running time and the quality of
- To obtain knowledge on the theory of combinatorial optimization
- To apply the theory to specific optimization problems. For example, by
analyzing the running time or performance guarantee of a given algorithm
or by constructing an own algorithm.
- To model problems (for example by integer linear programming) and to
solve them using optimization software.
Graph theory, integer linear programming, network optimization
algorithms, (matching, maximum flow, minimum cost flow, traveling
salesman problem, vehicle routing), complexity of optimization
(NP-hardness) approximation algorithms, dynamic programming, local
optimization, randomized algorithms.
Teaching MethodsLectures + Tutorials
Method of AssessmentWritten exam (50%) + assignments (50%)
For both parts, a minumum score of 5.0 (out of 10) is required.
Entry RequirementsOperations Research (X_400618)
LiteratureLecture notes (available on Canvas)
Book (required): Algorithms by Dasgupta, Papadimitriou, and Vazirani
(2006). ISBN 9780073523408
Recommended background knowledgeFamiliar with some basic optimization problems like shortest path,
maximum flow, or knapsack.
Basic knowledge of optimization techniques like linear programming and
Some programming experience, for example in Python or Java.
|Language of Tuition||English|
|Faculty||Faculty of Science|
|Course Coordinator||dr. ir. R.A. Sitters|
|Examiner||dr. ir. R.A. Sitters|
dr. ir. R.A. Sitters
You need to register for this course yourself
Last-minute registration is available for this course.
|Teaching Methods||Seminar, Lecture|
This course is also available as: