A decomposition based on path sets for the Multi-Commodity k-splittable Maximum Flow Problem

    Research output: Book/ReportReportResearch

    279 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 routed flow is maximized. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. In the literature, the problem is solved to optimality using branch-and-price algorithms built on path-based Dantzig-Wolfe decompositions. This paper proposes a new branch-and-price algorithm built on a path set-based Dantzig-Wolfe decomposition. A path set consists of up to k paths, each carrying a certain amount of flow. The new branch-and-price algorithm is implemented and compared to the leading algorithms in the literature. Results for the proposed method are competitive and the method even has best performance on some instances. However, the results also indicate some scaling issues.
    Original languageEnglish
    PublisherDTU Management Engineering
    Number of pages20
    ISBN (Electronic)978-87-92706-99-7
    Publication statusPublished - 2013
    SeriesDTU Management Engineering Report
    Number6.2013

    Keywords

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

    Fingerprint

    Dive into the research topics of 'A decomposition based on path sets for the Multi-Commodity k-splittable Maximum Flow Problem'. Together they form a unique fingerprint.

    Cite this