Combinatorial Optimization

2019-2020
Dit vak wordt in het Engels aangeboden. Omschrijvingen kunnen daardoor mogelijk alleen in het Engels worden weergegeven.

Doel vak

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.

Inhoud vak

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.

Onderwijsvorm

Lectures + Tutorials

Toetsvorm

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

Vereiste voorkennis

Operations Research (X_400618)

Literatuur

Lecture notes (available on Canvas)

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

Doelgroep

3BA

Aanbevolen voorkennis

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.

Algemene informatie

Vakcode X_401067
Studiepunten 6 EC
Periode P4+5
Vakniveau 300
Onderwijstaal Engels
Faculteit Faculteit der Bètawetenschappen
Vakcoördinator dr. ir. R.A. Sitters
Examinator dr. ir. R.A. Sitters
Docenten dr. ir. R.A. Sitters

Praktische informatie

Voor dit vak moet je zelf intekenen.

Voor dit vak kun je last-minute intekenen.

Werkvormen Werkcollege, Deeltoets extra zaalcapaciteit, Hoorcollege
Doelgroepen

Dit vak is ook toegankelijk als: