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 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
ratio)
- apply the theory by implementing some of these algorithms.
- construct and implement (in Python) your own algorithms for
optimization problems.

Inhoud vak

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.

Onderwijsvorm

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

Toetsvorm

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.

Vereiste voorkennis

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.

Literatuur

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.

Doelgroep

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

Aanbevolen voorkennis

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.

Algemene informatie

Vakcode E_EORM_COPT
Studiepunten 6 EC
Periode P1
Vakniveau 400
Onderwijstaal Engels
Faculteit School of Business and Economics
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, Hoorcollege, Computerpracticum
Doelgroepen

Dit vak is ook toegankelijk als: