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

作     者：Crainic, TG Frangioni, A Gendron, B 

作者机构：Univ Montreal Ctr Rech Transports Montreal PQ H3C 3J7 Canada Univ Quebec Dept Sci Adm Montreal PQ H3C 3P8 Canada 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2001年第112卷第1-3期

页      面：73-99页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Fonds F.C.A.R N.S.E.R.C. (Canada) 

主　　题：multicommodity capacitated fixed-charge network design Lagrangian relaxation sub-gradient methods bundle methods 

摘      要：To efficiently derive bounds for large-scale instances of the capacitated fixed-charge network design problem, Lagrangian relaxations appear promising. This paper presents the results of comprehensive experiments aimed at calibrating and comparing bundle and subgradient methods applied to the optimization of Lagrangian duals arising from two Lagrangian relaxations. This study substantiates the fact that bundle methods appear superior to subgradient approches because they converge faster and are more robust relative to different 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-charge 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 Science B.V. All rights reserved.