Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design. (English) Zbl 1483.90128
Summary: 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.
References:
| [1] | Amor, H. M.B.; Desrosiers, J.; Frangioni, A., On the choice of explicit stabilizing terms in column generation, Discrete Appl. Math., 157, 6, 1167-1184 (2009) · Zbl 1169.90395 |
| [2] | Atamtürk, A., Flow pack facets of the single node fixed-charge flow polytope, Oper. Res. Lett., 29, 3, 107-114 (2001) · Zbl 1018.90060 |
| [3] | Babonneau, F.; du Merle, O.; Vial, J.-P., Solving large-scale linear multicommodity flow problems with an active set strategy and proximal-accpm, Oper. Res., 54, 1, 184-197 (2006) · Zbl 1167.90661 |
| [4] | Chouman, M.; Crainic, T. G., A MIP-tabu search hybrid framework for multicommodity capacitated fixed-charge network design, (Publication CIRRELT 2010-31 (2010), Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation) |
| [5] | Chouman, M.; Crainic, T. G.; Gendron, B., Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed-charge network design, Transp. Sci., 51, 2, 650-667 (2016) |
| [6] | Chouman, M.; Crainic, T. G.; Gendron, B., The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design, EURO J. Comput. Optim., 6, 2, 1-42 (2017) |
| [7] | Costa, A. M.; Cordeau, J.-F.; Gendron, B., Benders, metric and cutset inequalities for multicommodity capacitated network design, Comput. Optim. Appl., 42, 3, 371-392 (2009) · Zbl 1208.90026 |
| [8] | Costa, A. M.; Cordeau, J.-F.; Gendron, B.; Laporte, G., Accelerating benders decomposition with heuristicmaster problem solutions, Pesqui. Oper., 32, 1, 03-20 (2012) · Zbl 1255.90083 |
| [9] | Crainic, T. G.; Frangioni, A.; Gendron, B., Bundle-based relaxation methods for multicommodity capacitated fixed charge network design, Discrete Appl. Math., 112, 1, 73-99 (2001) · Zbl 1026.90010 |
| [10] | Crainic, T. G.; Gendreau, M., Cooperative parallel tabu search for capacitated network design, J. Heuristics, 8, 6, 601-627 (2002) |
| [11] | Crainic, T. G.; Gendreau, M., A scatter search heuristic for the fixed-charge capacitated network design problem, (Doerner, K.; Gendreau, M.; Greistorfer, P.; Gutjahr, W. J.; Hartl, R. F.; Reismann, M., Metaheuristics - Progress in Complex Systems Optimization (2007), Springer: Springer Dordrecht), 25-40 · Zbl 1172.90337 |
| [12] | Crainic, T. G.; Gendreau, M.; Farvolden, J. M., A simplex-based tabu search method for capacitated network design, INFORMS J. Comput., 12, 3, 223-236 (2000) · Zbl 1040.90506 |
| [13] | Crainic, T. G.; Gendron, B.; Hernu, G., A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, J. Heuristics, 10, 5, 525-545 (2004) · Zbl 1062.90009 |
| [14] | Crainic, T. G.; Li, Y.; Toulouse, M., A first multilevel cooperative algorithm for capacitated multicommodity network design, Comput. Oper. Res., 33, 9, 2602-2622 (2006) · Zbl 1086.90009 |
| [15] | Dongarra, J. J., Performance of Various Computers using Standard Linear Equations SoftwareTechnical report (2014), University of Manchester |
| [16] | Fischetti, M.; Ljubić, I.; Sinnl, M., Benders decomposition without separability: A computational study for capacitated facility location problems, European J. Oper. Res., 253, 3, 557-569 (2016) · Zbl 1346.90490 |
| [17] | Frangioni, A.; Gendron, B.; Gorgone, E., On the computational efficiency of subgradient methods: a case study with lagrangian bounds, Math. Program. Comput., 1-32 (2017) |
| [18] | Frangioni, A.; Gorgone, E., Bundle methods for sum-functions with “easy” components: applications to multicommodity network design, Math. Program., 145, 1-2, 133-161 (2014) · Zbl 1300.90027 |
| [19] | Gendron, B., Revisiting Lagrangian relaxation for network design, Discrete Appl. Math. (2018) |
| [20] | Gendron, B.; Crainic, T. G., Relaxations for multicommodity capacitated network design problems, (Publication CRT-965 (1994), Centre for Research on Transportation) |
| [21] | Gendron, B.; Crainic, T. G.; Frangioni, A., Multicommodity capacitated network design, (Soriano, P.; Sansò, B., Telecommunications Network Planning (1999), Kluwer Academics Publisher: Kluwer Academics Publisher Dordrecht), 1-19 |
| [22] | Gendron, B.; Gouveia, L., Reformulations by discretization for piecewise linear integer multicommodity network flow problems, Transp. Sci., 51, 2, 629-649 (2016) |
| [23] | Gendron, B.; Hanafi, S.; Todosijević, R., Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design, European J. Oper. Res., 268, 1, 70-81 (2018) · Zbl 1403.90199 |
| [24] | Gendron, B.; Larose, M., Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design, EURO J. Comput. Optim., 2, 1-2, 55-75 (2014) · Zbl 1307.90117 |
| [25] | Geoffrion, A., Lagrangean relaxation for integer programming, Math. Program. Study, 2, 82-114 (1974) · Zbl 0395.90056 |
| [26] | Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Oper. Res., 51, 4, 655-667 (2003) · Zbl 1165.90360 |
| [27] | Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design, Ann. Oper. Res., 131, 1, 109-133 (2004) · Zbl 1067.90014 |
| [28] | Guignard, M.; Kim, S., Lagrangean decomposition: A model yielding stronger lagrangean bounds, Math. Program., 39, 2, 215-228 (1987) · Zbl 0638.90074 |
| [29] | Hewitt, M.; Nemhauser, G. L.; Savelsbergh, M. W., Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem, INFORMS J. Comput., 22, 2, 314-325 (2010) · Zbl 1243.90031 |
| [30] | Holmberg, K.; Yuan, D., A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem, Oper. Res., 48, 3, 461-481 (2000) · Zbl 1106.90381 |
| [31] | Katayama, N., A combined capacity scaling and local branching approach for capacitated multi-commodity network design problem, Far East J. Appl. Math., 92, 1, 1 (2015) · Zbl 1325.90015 |
| [32] | Katayama, N.; Chen, M.; Kubo, M., A capacity scaling heuristic for the multicommodity capacitated network design problem, J. Comput. Appl. Math., 232, 1, 90-101 (2009) · Zbl 1178.90057 |
| [33] | Kliewer, G.; Timajev, L., Relax-and-cut for capacitated network design, (Proceedings of Algorithms-ESA 2005: 13th Annual European Symposium on Algorithms. Proceedings of Algorithms-ESA 2005: 13th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 3369 (2005)), 47-58 · Zbl 1162.90576 |
| [34] | Klose, A., Algorithms for solving the single-sink fixed-charge transportation problem, Comput. Oper. Res., 35, 6, 2079-2092 (2008) · Zbl 1139.90008 |
| [35] | Paraskevopoulos, D. C.; Bektaş, T.; Crainic, T. G.; Potts, C. N., A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem, European J. Oper. Res., 253, 2, 265-279 (2016) · Zbl 1346.90224 |
| [36] | Rodríguez-Martín, I.; José Salazar-González, J., A local branching heuristic for the capacitated fixed-charge network design problem, Comput. Oper. Res., 37, 3, 575-581 (2010) · Zbl 1175.90072 |
| [37] | Sellmann, M.; Kliewer, G.; Koberstein, A., Lagrangian cardinality cuts and variable fixing for capacitated network design, (Proceedings of Algorithms-ESA 2002: 10th Annual European Symposium on Algorithms. Proceedings of Algorithms-ESA 2002: 10th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 2461 (2002)), 845-858 · Zbl 1040.90004 |
| [38] | Yaghini, M.; Rahbar, M.; Karimi, M., A hybrid simulated annealing and column generation approach for capacitated multicommodity network design, J. Oper. Res. Soc., 64, 7, 1010-1020 (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
