Two- and three-index formulations of the minimum cost multicommodity k-splittable flow problem

Mette Gamst, Peter Neergaard Jensen, David Pisinger, Christian Edinger Munk Plum

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The multicommodity flow problem (MCFP) considers the efficient routing of commodities from their origins to their destinations subject to capacity restrictions and edge costs. Baier et al. [G. Baier, E. Köhler, M. Skutella, On the k-splittable flow problem, in: 10th Annual European Symposium on Algorithms, 2002, 101–113] introduced the maximum flow multicommodity k-splittable flow problem (MCkFP) where each commodity may use at most k paths between its origin and its destination. This paper studies the -hard minimum cost multicommodity k-splittable flow problem (MCMCkFP) in which a given flow of commodities has to be satisfied at the lowest possible cost. The problem has applications in transportation problems where a number of commodities must be routed, using a limited number of distinct transportation units for each commodity. Based on a three-index formulation by Truffot et al. [J. Truffot, C. Duhamel, P. Mahey, Branch and price pour le problème du multiflot k-séparable de coût minimal, in: LIMOS, UMR 6158 – CNRS, ROADEF’05, 2005] we present a new two-index formulation for the problem, and solve both formulations through branch-and-price. The three-index algorithm by Truffot et al. is improved by introducing a simple heuristic method to reach a feasible solution by eliminating some symmetry. A novel branching strategy for the two-index formulation is presented, forbidding subpaths in the branching children. Though the proposed heuristic for the three-index algorithm improves its performance, the three-index algorithm is still outperformed by the two-index algorithm, both with respect to running time and to the number of solved test instances.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Volume202
    Issue number1
    Pages (from-to)82-89
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2010

    Keywords

    • network flows
    • multicommodity flow
    • decomposition
    • transportation

    Fingerprint Dive into the research topics of 'Two- and three-index formulations of the minimum cost multicommodity k-splittable flow problem'. Together they form a unique fingerprint.

    Cite this