A route-based decomposition for the Multi-Commodity k-splittable Maximum Flow Problem

Mette Gamst

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    120 Downloads (Pure)

    Abstract

    The Multi-Commodity k-splittable Maximum Flow Problem routes flow through a capacitated graph such that each commodity uses at most k paths and such that the total amount of routedflow is maximized. This paper proposes a branch-and-price algorithm based on a route-based Dantzig-Wolfe decomposition, where a route consists of up to k paths. Computational results show that the new algorithm has best performance on seven benchmark instances and is capable of solving two previously unsolved instances.
    Original languageEnglish
    Title of host publicationProceedings
    Number of pages4
    Publication date2012
    Publication statusPublished - 2012
    Event2nd International Symposium on Combinatorial Optimization (ISCO 2012) - Athens, Greece
    Duration: 17 Apr 201221 Apr 2012

    Conference

    Conference2nd International Symposium on Combinatorial Optimization (ISCO 2012)
    CountryGreece
    CityAthens
    Period17/04/201221/04/2012

    Keywords

    • Branch and price
    • Dantzig-Wolfe Decomposition
    • Multi-commodity flow
    • k-splittable
    • Combinatorial optimization

    Fingerprint Dive into the research topics of 'A route-based decomposition for the Multi-Commodity <em>k</em>-splittable Maximum Flow Problem'. Together they form a unique fingerprint.

    Cite this