Bundle-based relaxation methods for multicommodity capacitated fixed charge network design

To efficiently derive bounds for large-scale instances of the capacitated f ixed-charge network design problem, Lagrangian relaxations appear promising . This paper presents the results of comprehensive experiments aimed at cal ibrating and comparing bundle and subgradient methods applied to the optimi zation of Lagrangian duals arising from two Lagrangian relaxations. This st udy substantiates the fact that bundle methods appear superior to subgradie nt approches because they converge faster and are more robust relative to d ifferent relaxations, problem characteristics, and selection of the initial parameter values. It also demonstrates that effective lower bounds may be computed efficiently for large-scale instances of the capacitated fixed-cha rge network design problem. Indeed, in a fraction of the time required by a standard simplex approach to solve the linear programming relaxation, the methods we present attain very high-quality solutions. (C) 2001 Elsevier Sc ience B.V. All rights reserved.