Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM

Frédéric Babonneau (frederic.babonneauhec.unige.ch)
Olivier du Merle (Olivier du Merle:oldumerleairfrance.fr)
Jean-Philippe Vial (jean-philippe.vialhec.unige.ch)

Abstract: 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 it appears to be the case in many practical problems.

Keywords: Multicommodity flows, Active set, ACCPM

Category 1: Network Optimization

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: Technical report, Logilab, HEC, Universit\'e de Gen\`eve, 40 Bd du Pont d'Arve, CH-1211 Geneva, Switzerland.

Download: [PDF]

Entry Submitted: 06/17/2004
Entry Accepted: 08/05/2004
Entry Last Modified: 06/17/2004

Modify/Update this entry