Prerequisites

Basic knowledge (bachelor level) of linear algebra, discrete optimization and linear programming (for this, we refer to W.L. Winston, Operations Research - Applications and Algorithms, 4th edition, Chapters 1-9, 18); general academic skills (bachelor level) like extracting relevant aspects related to the content touched in the lectures from given literature and writing reports. Besides for students from a Mathematics program, the course is also suitable for students of other programs (such as Econometrics and Industrial Engineering & Management) if they have a solid background in Mathematics.

Aim of the course

This course gives an overview of general applicable and practically useful heuristic solution methods in combinatorial optimization

Description

Due to the computational complexity of most of the practical relevant optimization problems, heuristic methods form an important class of solution methods for such problems. In this course we give an overview of different classes of heuristic solution approaches and present examples of their application.

In detail, the following issues are treated:

- Sampling based heuristics
- Restricted dynamic programming
- Truncated branch and bound/beam search
- Relaxations/lower bounds
- Evaluation techniques
- Local search
- Evolutionary methods

For some methods the focus is on the mathematical background and some theory. For other parts the focus is on the applicability in practice. In the final lecture both parts are brought together in an interactive lecture.

- Docent: Johann Hurink