Combining Metaheuristics with Mathematical Programming: Techniques for Solving Difficulty Network Design Problems

Speaker: Prof. Gunther Raidl

Abstract

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.

Brief Bio

Dr. Gunther Raidl is Full professorship for combinatorial optimization at the Vienna University of Technology, Vienna Austria

His research interests include:

• Solving algorithmic problems arising in various application domains, e.g. network design and other problems on graphs, cutting and packing, computational biology, scheduling, routing.
• Combinatorial optimization by means of metaheuristics including evolutionary computation and exact techniques, like branch and bound, polyhedral combinatorics, and integer linear programming.
• A current particular focus is the hybridization of integer linear programming based methods and meta-heuristics.
• Major application areas I consider are e.g. cutting and packing and network design.
• Efficient algorithms and data structures in general.
• Various other topics in the field of computer algorithms, computer graphics, system software, Linux, networking, and hardware.

His more recent peer-esteem indicators are:

• Editor-in-Chief of GECCO 2009, the Genetic and Evolutionary Computation Conference 2009, Montreal, Canada, July 2009.
• Associate editor of the Evolutionary Computation Journal, MIT Press, since January 2005.
• Associate editor of the International Journal of Metaheuristics, Inderscience, since October 2007.
• Editorial board member of the journal Journal of Artificial Evolution and Applications, Hindawi Publishing, since January 2007.
• Editorial board member of the journal Memetic Computing, Springer, since October 2007.
• Editorial board member of the Journal of Applied Metaheuristic Computing, IGI Global, first issue to be released 2010 # Co-founder and member of the steering committee of the Conference Series on Evolutionary Computation in Combinatorial Optimization, EvoCOP. The next event, EvoCOP 2008, will take place in Naples, Italy on 26-28 March, 2008.