040676 KU Metaheuristics (MA) (2021S)

Metaheuristics are general high-level procedures that coordinate simple heuristics and rules to find high-quality solutions to difficult optimization problems. They are based on distinct paradigms and offer different mechanisms to go beyond the first solution obtained that cannot be improved by local search. They are frequently built upon a number of common building blocks such as greedy algorithms, randomization, neighborhoods and local search, reduced neighborhoods and candidate lists, intensification, diversification, path-relinking, and periodical restarts. Metaheuristics are among the most effective solution strategies for solving combinatorial optimization problems in practice and very frequently produce much better solutions than those obtained by the simple heuristics and rules they coordinate.
Metaheuristics are particularly attractive in the efficient and effective solution of logistic decision problems in supply chains, transportation, telecommunications, vehicle routing and scheduling, manufacturing and machine scheduling, timetabling, sports scheduling, facility location and layout, and network design, among other areas.

The objective of this course is to provide students with the fundamental tools for designing, tuning, and testing heuristics and metaheuristics for hard combinatorial optimization problems. Besides that, we will also cover the fundamental concepts of complexity theory that are the key to understanding the need for approximate approaches and to design efficient heuristics and metaheuristics.
1. A gentle introduction to the analysis of algorithms and complexity theory
2. Historical and modern local search methods
3. Nature-inspired metaheuristics
4. Construction-based metaheuristics