Tutorials

Hybrid Metaheuristics and Matheuristics - Günther Raidl

Institute of Computer Graphics and Algorithms - Vienna University of Technology - Austria

It is well known that for many practical optimization problems, especially from the domain of combinatorial optimization, "pure" evolutionary algorithms, simulated annealing, tabu search, and other metaheuristics are frequently not as effective as more sophisticated hybrid approaches. Such hybrids may combine concepts from different metaheuristics, exact optimization techniques, problem-specific procedures, and even methods from other fields such as artificial intelligence or operations research. The general idea is to "exploit the best of different worlds" and to benefit from synergy by such combinations. Numerous publications from the recent years and dedicated scientific workshops document the significance of this trend and specific research area.

This tutorial starts with an overview on the most commonly used hybridization techniques such as embedding local search procedures in evolutionary algorithms, very large neighborhood search, and solution merging. A systematic classification of hybrid approaches will then be discussed, leading to further approaches, especially also collaborative combinations, in which different search strategies cooperate in a looser form.

In the second part we will focus on combinations of metaheuristics with (integer) linear programming methods, i.e. matheuristics. Discussed topics include solution merging, strategic guidance of metaheuristics by means of linear programming and Lagrangian relaxations, and exploiting metaheuristics within exact branch-and-bound frameworks. Last but not least, some less common but sometimes very powerful strategies such as applying metaheuristics for cut and column generation are addressed.

Problem decomposition in metaheuristics - Eric Taillard

University of Applied Sciences of Western - Switzerland

The basic components of metaheuristics are very few: In addition to problem modelling, which is not proper to metaheuristics, the most general components studied are solution building, solution improvement and learning mechanisms. When dealing with large problem instances, decomposition methods are the only viable way to produce solutions with moderate computational effort, but these methods are somewhat overwhelmed. Problem decomposition may be used for solution building or solution improvement. Two templates are reviewed for solution improvement: large neighbourhood search (LNS) and POPMUSIC. For solution building, a new method embedding clustering with POPMUSIC is presented. Applications to map labelling and location routing are reported.

Cellular genetic algorithms - Enrique Alba

University of Malaga - Spain

Cellular GAs are a new class of optimization, search, and learning algorithms that allow a flexible balance between exploration and exploitation by using overlapped search neighborhoods. Their population is made of such small neighborhoods inside which solutions interact in micro-GAs, while the sharing of a solution between several neighborhoods allow a smooth diffusion of the best points along the population. Cellular GAs foster methodological and fundamental research, as well as they can be used in dynamic and multiobjective problems. Parallelism is a close issue in this domain, opening new lines in manycore systems and especially in GPUs. The amazing interactions and emerging behavior of this swarm intelligence technique have already provided competitive results in varied domains like communications, bioinformatics, combinatorial optimization, logistics, and continuous optimization, among others. This talk will present their basics and several illustrative examples of application to grasp the actual power of this kind of structured population techniques.