A Benders decomposition based framework for solving cable trench problems. (English) Zbl 1391.90505

Summary: In this work, we present an algorithmic framework based on Benders decomposition for the capacitated \(p\)-cable trench problem with covering. We show that our approach can be applied to most variants of the cable trench problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate the convergence of the cut loop and with a primal heuristic to derive high-quality primal solutions. Three different variants of the CTP are considered in a computational study which compares the Benders approach with two compact integer linear programming formulations that are solved with CPLEX. The obtained results show that the proposed algorithm significantly outperforms the two compact models and that it can be used to tackle significantly larger instances than previously considered algorithms based on Lagrangean relaxation.


90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90B10 Deterministic network models in operations research
90B80 Discrete location and assignment
Full Text: DOI Link


[1] Discrete location problems: benchmark library. http://www.math.nsc.ru/AP/benchmarks/english.html; Accessed: 2015-07-14.
[2] Beasley, J., OR-library: distributing test problems by electronic mail, J Oper Res Soc, 41, 11, 1069-1072, (1990)
[3] Ben-Ameur, W.; Neto, J., Acceleration of cutting-plane and column generation algorithms: applications to network design, Networks, 49, 1, 3-17, (2007) · Zbl 1131.90047
[4] Benders, J., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252, (1962) · Zbl 0109.38302
[5] Cherkassky, B.; Goldberg, A., On implementing push-relabel method for the maximum flow problem, (Balas, E.; Clausen, J., Proceedings of IPCO IV, LNCS, 920, (1995), Springer), 157-171
[6] Chimani, M.; Gutwenger, C.; Jünger, M.; Klau, G.; Klein, K.; Mutzel, P., The open graph drawing framework (OGDF), Handbook of graph drawing and visualization, 543-569, (2011)
[7] Dijkstra, E., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 1, 269-271, (1959) · Zbl 0092.16002
[8] Fischetti, M.; Ljubić, I.; Sinnl, M., Redesigning benders decomposition for large scale facility location, Manage Sci, (2016)
[9] Floyd, R., Algorithm 97: shortest path, Commun ACM, 5, 6, (1962)
[10] Gouveia, L., A comparison of directed formulations for the capacitated minimal spanning tree, Telecommun Syst, 1, 51-76, (1993)
[11] Hakimi, S., Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Oper Res, 13, 3, 462-475, (1965) · Zbl 0135.20501
[12] Jiang, Y.; Zhuang, Z.; Sinusas, A.; Papademetris, X., Vascular tree reconstruction by minimizing a physiological functional cost, 2010 IEEE Computer society conference on computer vision and pattern recognition-workshops, 178-185, (2010), IEEE
[13] Jiang, Y.; Zhuang, Z.; Sinusas, A.; Staib, L.; Papademetris, X., Vessel connectivity using murray’s hypothesis, International conference on medical image computing and computer-assisted intervention, 528-536, (2011), Springer
[14] Lalla-Ruiz, E.; Schwarze, S.; Voß, S., A matheuristic approach for the p-cable trench problem, Learning and intelligent optimization: 10th international conference, LION 10, 247-252, (2016)
[15] Lorena, L.; Senne, E., A column generation approach to capacitated p-Median problems, Comput Oper Res, 31, 6, 863-876, (2004) · Zbl 1048.90132
[16] Marianov, V.; Gutiérrez-Jarpa, G.; Obreque, C.; Cornejo, O., Lagrangean relaxation heuristics for the p-cable-trench problem, Comput Oper Res, 39, 3, 620-628, (2012) · Zbl 1251.90248
[17] Marianov, V.; Gutiérrez-Jarpa, G.; Obreque, C., p-cable trench problem with covering, XXII EURO working group on locational analysis meeting, 75-76, (2015)
[18] Minieka, E., The m-center problem, SIAM Rev, 12, 1, 138-139, (1970) · Zbl 0193.24204
[19] Schwarze, S., The multi-commodity cable trench problem, ECIS 2015 Completed research papers, (2015)
[20] Vasko, F.; Barbieri, R.; Rieksts, B.; Reitmeyer, K.; Stott, K., The cable trench problem: combining the shortest path and minimum spanning tree problems, Comput Oper Res, 29, 5, 441-458, (2002) · Zbl 0994.90124
[21] Vasko, F.; Landquist, E.; Kresge, G.; Tal, A.; Jiang, Y.; Papademetris, X., A simple and efficient strategy for solving very large-scale generalized cable-trench problems, Networks, 67, 3, 199-208, (2016)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.