This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Babonneau, F. Articles by Vial, J.-P. Search for Related Content

Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM

Logilab, HEC, Université de Genève, 40 Bd du Pont d’Arve, CH-1211 Geneva, Switzerland
Air France, Operations Research Department, 1 Avenue du Maréchal Devaux, 91550 Paray-Vieille-Poste, France
Logilab, HEC, Universitè de Genéve, 40 Bd du Pont d’Arve, CH-1211 Geneva, Switzerland
frederic.babonneau{at}hec.unige.ch
oldumerle{at}airfrance.fr
jean-philippe.vial{at}hec.unige.ch

In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to be the case in many practical problems.

Subject classifications: network; linear multicommodity flow; analytic center cutting-plane method; active set strategy.
History: Received July 2004; revision received October 2004; accepted December 2004.

This article has been cited by other articles:

				F. Babonneau and J.-P. Vial Test Instances for the Multicommodity Flow Problem: An Erratum Operations Research, July 1, 2009; 57(4): 1045 - 1045. [Abstract] [PDF]

				F. Babonneau and J.-P. Vial An Efficient Method to Compute Traffic Assignment Problems with Elastic Demands Transportation Science, May 1, 2008; 42(2): 249 - 260. [Abstract] [PDF]