An Exact Solution Approach for the Maximum Multicommodity K-splittable Flow Problem

Mette Gamst (Invited author), Bjørn Petersen (Invited author)

    Research output: Chapter in Book/Report/Conference proceedingConference abstract in proceedingsResearch

    920 Downloads (Pure)

    Abstract

    This talk concerns the NP-hard Maximum Multicommodity k-splittable Flow Problem (MMCkFP) in which each commodity may use at most k paths between its origin and its destination. A new branch-and-cut-and-price algorithm is presented. The master problem is a two-index formulation of the MMCkFP and the pricing problem is the shortest path problem with forbidden paths. A new branching strategy forcing and forbidding the use of certain paths is developed. The new branch-and-cut-and-price algorithm is computationally evaluated and compared to results from the literature. The new algorithm shows very promising performance by outperforming existing algorithms for several instances.
    Original languageEnglish
    Title of host publicationProceedings of the 20th International Symposium of Mathematical Programming 2009 (ISMP'09)
    Publication date2009
    Publication statusPublished - 2009
    Event20th International Symposium of Mathematical Programming - Chicago, IL, United States
    Duration: 23 Aug 200928 Aug 2009
    Conference number: 20
    http://ismp2009.eecs.northwestern.edu/

    Conference

    Conference20th International Symposium of Mathematical Programming
    Number20
    Country/TerritoryUnited States
    CityChicago, IL
    Period23/08/200928/08/2009
    Internet address

    Fingerprint

    Dive into the research topics of 'An Exact Solution Approach for the Maximum Multicommodity K-splittable Flow Problem'. Together they form a unique fingerprint.

    Cite this