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

P. Chardaire and A. Lisser ()
Additional contact information
P. Chardaire: School of Information Systems, University of East Anglia, Norwich NR4 7TJ, United Kingdom
A. Lisser: Laboratoire de Recherche en Informatique, Bât 490, Université Paris Sud, 91405 Orsay Cedex, France

Operations Research, 2002, vol. 50, issue 2, 260-276

Abstract: 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.

Keywords: Networks/graphs; multicommodity: solution of network routing problems; Programming/linear; large scale systems: solution of multicommodity flow problems (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.2.260.436 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:2:p:260-276

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().