Skip to Main content Skip to Navigation
Book sections

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.
Document type :
Book sections
Complete list of metadata
Contributor : Jakob Puchinger Connect in order to contact the contributor
Submitted on : Monday, November 9, 2015 - 6:29:08 PM
Last modification on : Wednesday, October 13, 2021 - 7:58:04 PM



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⟩



Les métriques sont temporairement indisponibles