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.
|
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: | 06 Oct 2023 01:57 |
| DOI: | 10.1016/j.dam.2020.12.024 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3111786 |
Dimensions
Dimensions
