MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics

Jakob Puchinger, G. Raidl, S. Pirkwieser

    Research output: Chapter in Book or Conference ProceedingsBook chapter


    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.
    Original languageEnglish
    Title of host publicationMatheuristics: Hybridizing Metaheuristics and Mathematical Programming
    Number of pages32
    ISBN (Print)978-1-4419-1305-0
    Publication statusPublished - 2009

    Research Field

    • Former Research Field - Mobility Systems


    Dive into the research topics of 'MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics'. Together they form a unique fingerprint.

    Cite this