[Zurück]

G. Raidl:
"Combining Metaheuristics with Mathematical Programming Techniques for Solving Difficult Network Design Problems";
Hauptvortrag: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Znaim, Tschechien (eingeladen); 13.11.2009 - 15.11.2009.

While mathematical programming techniques are powerful approaches for solving hard combinatorial optimization problems appearing in the area of network design, their application is usually limited to instances of small or moderate size due to their exhaustive running time and memory requirements. In practice, one usually has to turn to heuristic and metaheuristic approaches for approximately solving larger instances. Over the last years so-called hybrid optimization techniques have become more popular. They combine concepts of different optimization strategies and try to exploit their individual benefits. Various examples illustrate that often such hybrids are indeed able to outperform their "pure" counterparts. This talk gives an overview on successful hybridization techniques with a particular focus on combinations of metaheuristics and integer linear programming (ILP) methods. We will then consider a few case studies, including approaches where very large neighborhoods are searched by means of ILP methods, a Lagrangian decomposition approach collaborates with variable neighborhood search, and a column generation algorithm is sped up by means of metaheuristics. These examples document the usefulness and large potential such combinations have.