Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design

Kazemzadeh, Mohammad Rahim Akhavan, Bektas, Tolga ORCID: 0000-0003-0634-144X, Crainic, Teodor Gabriel, Frangioni, Antonio, Gendron, Bernard and Gorgone, Enrico (2022) Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design DISCRETE APPLIED MATHEMATICS, 308. pp. 255-275. ISSN 0166-218X, 1872-6771

Text Paper_Node_Lag-DAM-V2-R.pdf - Author Accepted Manuscript Download (374kB) | Preview

Abstract

Classical Lagrangian relaxations for the multicommodity capacitated fixed-charge network design problem are the so-called flow and knapsack relaxations, where the resulting Lagrangian subproblems decompose by commodities and by arcs, respectively. We introduce node-based Lagrangian relaxations, where the resulting Lagrangian subproblem decomposes by nodes. We show that the Lagrangian dual bounds of these relaxations improve upon the linear programming relaxation bound, known to be equal to the Lagrangian dual bounds for the flow and knapsack relaxations. We also develop a Lagrangian matheuristic to compute upper bounds. The computational results on a set of benchmark instances show that the Lagrangian matheuristic is competitive with the state-of-the-art heuristics from the literature.

Item Type:	Article
Uncontrolled Keywords:	Network design, Lagrangian relaxation, Column generation, Matheuristic
Depositing User:	Symplectic Admin
Date Deposited:	13 Jan 2021 12:06
Last Modified:	16 Jun 2026 13:27
DOI:	10.1016/j.dam.2020.12.024
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3111786
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.