Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods

Autor: Rui Sa Shibasaki, Philippe Mahey, Francisco Barahona, Mauricio C. de Souza, Mourad Baïou
Přispěvatelé: Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Mathematical optimization
021103 operations research
fixed-charge multicommodity network design problem
Computer science
Heuristic
Strategy and Management
0211 other engineering and technologies
Volume (computing)
Scale (descriptive set theory)
02 engineering and technology
Function (mathematics)
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Management Science and Operations Research
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Constructive
Computer Science Applications
Dual (category theory)
Network planning and design
Management of Technology and Innovation
Bundle
0202 electrical engineering
electronic engineering
information engineering
Bundle method
020201 artificial intelligence & image processing
Business and International Management
Volume algorithm
Zdroj: International Transactions in Operational Research
International Transactions in Operational Research, 2021, 28 (1), pp.296-326. ⟨10.1111/itor.12770⟩
International Transactions in Operational Research, Wiley, 2021, 28 (1), pp.296-326. ⟨10.1111/itor.12770⟩
ISSN: 0969-6016
1475-3995
DOI: 10.1111/itor.12770⟩
Popis: International audience; The Bundle Method and the Volume Algorithm are among the most efficient techniques to obtain accurate Lagrangian dual bounds for hard combinatorial optimization problems. We propose here to compare their performance on very large scale Fixed-Charge Multicommodity Capacitated Network Design problems. The motivation is not only the quality of the approximation of these bounds as a function of the computational time but also the ability to produce feasible primal solutions and thus to reduce the gap for very large instances for which optimal solutions are out of reach. Feasible solutions are obtained through the use of Lagrangian information in constructive and improving heuristic schemes. We show in particular that, if the Bundle implementation has provided great quality bounds in fewer iterations, the Volume Algorithm is able to reduce the gaps of the largest instances, taking profit of the low computational cost per iteration compared to the Bundle Method.
Databáze: OpenAIRE
Externí odkaz: