Simplex and interior point specialized algorithms for solving nonoriented multicommodity flow problems
成果类型：
Article
署名作者：
Chardaire, R; Lisser, A
署名单位：
University of East Anglia; Universite Paris Saclay
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.50.2.260.436
发表日期：
2002
页码：
260-276
关键词：
摘要：
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 flow problems. Algorithms are tested with data from the France-Telecom Paris district transmission network, First, we focus on a specialization for the node-are formulation of the problem. Primal simplex and Dual Affine Scaling algorithms exploiting the particular structure of the constraint matrix are presented and compared, Numerical results a-re provided for problems up to about 800,000 constraints and 6,000,000 variables. However, much more powerful approaches based on specialized decompostion 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.