Combinatorial Optimization

2019-2020

Course Objective

In 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
solutions.
Objectives:
- 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.

Course Content

Subjects:
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
search, online
optimization, randomized algorithms.

Teaching Methods

Lectures + Tutorials

Method of Assessment

Written exam (50%) + assignments (50%)
For both parts, a minumum score of 5.0 (out of 10) is required.

Entry Requirements

Operations Research (X_400618)

Literature

Lecture notes (available on Canvas)

Book (required): Algorithms by Dasgupta, Papadimitriou, and Vazirani
(2006). ISBN 9780073523408

Target Audience

3BA

Recommended background knowledge

Familiar with some basic optimization problems like shortest path,
maximum flow, or knapsack.
Basic knowledge of optimization techniques like linear programming and
dynamic programming.
Some programming experience, for example in Python or Java.

General Information

Course Code X_401067
Credits 6 EC
Period P4+5
Course Level 300
Language of Tuition English
Faculty Faculty of Science
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
Target audiences

This course is also available as: