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

Chardaire, P. and Lisser, A. (2002) Simplex and interior point specialized algorithms for solving non oriented multicommodity flow problems. Operations Research, 50 (2). pp. 260-276. ISSN 0030-364X

Full text not available from this repository.

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.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
Depositing User:	Vishal Gautam
Date Deposited:	27 Jul 2011 12:35
Last Modified:	20 Aug 2023 01:01
URI:	https://ueaeprints.uea.ac.uk/id/eprint/23402
DOI:	10.1287/opre.50.2.260.436

Actions (login required)

View Item