Simplex and interior point specialized algorithms for solving nonoriented multicommodity flow problems

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-arc 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 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. Partitioning techniques are used to exploit the structure of the master programs involved in those methods.