MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics

Abstract : This chapter reviews approaches where metaheuristics are used to boost the performance of exact integer linear programming (IP) techniques. Most exact optimization methods for solving hard combinatorial problems rely at some point on tree search. Applying more effective metaheuristics for obtaining better heuristic solutions and thus tighter bounds in order to prune the search tree in stronger ways is the most obvious possibility. Besides this, we consider several approaches where metaheuristics are integrated more tightly with IP techniques. Among them are collaborative approaches where various information is exchanged for providing mutual guidance, metaheuristics for cutting plane separation, and metaheuristics for column generation. Two case studies are finally considered in more detail: (i) a Lagrangian decomposition approach that is combined with an evolutionary algorithm for obtaining (almost always) proven optimal solutions to the knapsack constrained maximum spanning tree problem and (ii) a column generation approach for the periodic vehicle routing problem with time windows in which the pricing problem is solved by local search based metaheuristics.
Type de document :
Chapitre d'ouvrage
Matheuristics Hybridizing Metaheuristics and Mathematical Programming, 2010, 978-1-4419-1305-0. 〈10.1007/978-1-4419-1306-7_3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01226562
Contributeur : Jakob Puchinger <>
Soumis le : lundi 9 novembre 2015 - 18:29:08
Dernière modification le : lundi 9 novembre 2015 - 18:29:08

Identifiants

Citation

Jakob Puchinger, Günther Raidl, Sandro Pirkwieser. MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics. Matheuristics Hybridizing Metaheuristics and Mathematical Programming, 2010, 978-1-4419-1305-0. 〈10.1007/978-1-4419-1306-7_3〉. 〈hal-01226562〉

Partager

Métriques

Consultations de la notice

9