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

    647 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
    EventThe 20th International Symposium of Mathematical Programming 2009 (ISMP'09) - Chicago, US
    Duration: 1 Jan 2009 → …

    Conference

    ConferenceThe 20th International Symposium of Mathematical Programming 2009 (ISMP'09)
    CityChicago, US
    Period01/01/2009 → …

    Cite this

    Gamst, M., & Petersen, B. (2009). An Exact Solution Approach for the Maximum Multicommodity K-splittable Flow Problem. In Proceedings of the 20th International Symposium of Mathematical Programming 2009 (ISMP'09) http://ismp2009.eecs.northwestern.edu/printfiles/ScheduleFriday.pdf