040676 KU Metaheuristics (MA) (2017W)

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 first goal of this course is to give the students a general idea of the class of problems that are amenable to be efficiently solvable by metaheuristics. With this goal in view, the course starts by a gentle and intuitive introduction to complexity theory. The second goal is to present the main metaheuristics and their building blocks, so as that the students could be able to propose or even develop simple solution strategies for practical problems. The students will learn the main concepts relevant for the design and application of metaheuristics. Finally, the third goal consists in showing some applications of metaheuristics.
1. A gentle introduction to the analysis of algorithms and complexity theory
2. Greedy algorithms
3. Local search
4. Building blocks: randomization, intensification, path-relinking, diversification, restarts
5. Greedy randomized adaptive search procedures (GRASP)
6. Simulated annealing
7. Tabu search
8. Genetic algorithms
9. Application seminars: scheduling sports competitions, routing in transportation networks, private virtual circuit routing in communication networks, data mining