MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics

Jakob Puchinger, G. Raidl, S. Pirkwieser

    Publikation: Beitrag in Buch oder TagungsbandBuchkapitel


    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 e ective 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 nally 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.
    TitelMatheuristics: Hybridizing Metaheuristics and Mathematical Programming
    Herausgeber (Verlag)Springer
    ISBN (Print)978-1-4419-1305-0
    PublikationsstatusVeröffentlicht - 2009

    Research Field

    • Ehemaliges Research Field - Mobility Systems


    Untersuchen Sie die Forschungsthemen von „MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics“. Zusammen bilden sie einen einzigartigen Fingerprint.

    Diese Publikation zitieren