This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Chardaire, P. Articles by Lisser, A. Search for Related Content

Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow Problems

School of Information Systems, University of East Anglia, Norwich NR4 7TJ, United Kingdom
Laboratoire de Recherche en Informatique, Bât 490, Université Paris Sud, 91405 Orsay Cedex, France
lisser{at}lri.fr

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.

Subject classifications: Networks/graphs, multicommodity: solution of network routing problems; Programming/linear, large scale systems: solution of multicommodity flow problems.
History: Received October 1996; revision received November 1998; accepted July 2000.