Simplex and interior point specialized algorithms for solving non oriented multicommodity flow problems

P. Chardaire, A. Lisser

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


Multicommodity network flow models arise in a wide variety of contexts, typical among which is the dimensioning of telecommunication networks. In this paper, we present various approaches based on specialization of the simplex algorithm and interior-point methods to solve nonoriented multicommodity flowproblems. Algorithms are tested with data from the France-Telecom Paris district transmission network. First, we focus on a specialization for the node-arc formulation of the problem. A Primal simplex and Dual Affine Scaling algorithms exploiting the particular structure of the constraint matrix are presented and compared. Numerical results are provided for problems up to about 800,000 constraints and 6,000,000 variables. However, much more powerful approaches based on specialized decomposition methods can be implemented for solving the problem. A Dantzig-Wolfe decomposition method is designed and compared with a specialized implementation of the Analytic Center Cutting Plane Method (ACCPM). Partitioning techniques are used to exploit the structure of the master programs involved in those methods.
Original languageEnglish
Pages (from-to)260-276
Number of pages17
JournalOperations Research
Issue number2
Publication statusPublished - 2002

Cite this