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. [References: 40]
展开▼
