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

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.

Prerequisites

Basic knowledge (bachelor level) of linear algebra, discrete optimization and linear programming

Rules about Homework / Exam

The final mark combines the grades of two assignments (20%) and the mark of an oral examination (80%).

For the oral examination, dates in December 2017 and January 2018 will be announced. For both assignments a report with the findings has to be written, whereby the stated question of each assignment is quite open and leaves room for individual approaches.