Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design
Gorgone E.
2022-01-01
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.File | Size | Format | |
---|---|---|---|
CIRRELT-2021-01.pdf Solo gestori archivio
Type: versione pre-print
Size 1.21 MB
Format Adobe PDF
|
1.21 MB | Adobe PDF | & nbsp; View / Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.