Login | Register

Solving the Optimum Communication Spanning Tree Problem


Solving the Optimum Communication Spanning Tree Problem

Contreras, Ivan ORCID: https://orcid.org/0000-0002-0235-8108, Armando Zetina, Carlos, Fernández, Elena and Luna-Mota, Carlos (2017) Solving the Optimum Communication Spanning Tree Problem. European Journal of Operational Research . ISSN 03772217 (In Press)

Text (application/pdf)
Contreras 2018.pdf - Accepted Version
Available under License Spectrum Terms of Access.

Official URL: http://dx.doi.org/10.1016/j.ejor.2018.07.055


This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able to prove optimality for five unsolved instances in the literature and four from a new set of larger instances.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering
Item Type:Article
Authors:Contreras, Ivan and Armando Zetina, Carlos and Fernández, Elena and Luna-Mota, Carlos
Journal or Publication:European Journal of Operational Research
Date:6 December 2017
  • Canadian Natural Sciences and Engineering Research Council (NSERC)
  • Spanish Ministry of Economy and Competitiveness and ERDF
Digital Object Identifier (DOI):10.1016/j.ejor.2018.07.055
Keywords:Networks; Network optimization; Benders decomposition; Spanning trees
ID Code:984182
Deposited By: ALINE SOREL
Deposited On:22 Aug 2018 15:41
Last Modified:08 Aug 2020 00:00


Achterberg, Koch, Martin, 2005. T. Achterberg, T. Koch, A. MartinBranching rules revisited, Operations Research Letters, 33 (1) (2005), pp. 42-54, 10.1016/j.orl.2004.04.002

Ahuja, Magnanti, Orlin, 1993. R.K. Ahuja, T.L. Magnanti, J.B. OrlinNetwork Flows: Theory, Algorithms, and Applications Prentice-Hall, New Jersey, U.S.A. (1993)

Ahuja, Murty, 1987. R.K. Ahuja, V.V.S. MurtyExact and heuristic algorithms for the optimum communication spanning tree problem, Transportation Science, 21 (3) (1987), pp. 163-170, 10.1287/trsc.21.3.163

Ben-Ameur, Neto, 2007. W. Ben-Ameur, J. NetoAcceleration of cutting plane and column generation algorithms: Applications to network design,Networks, 49 (1) (2007), pp. 3-17

Benders, 1962. J.-F. BendersPartitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4 (1962), pp. 238-252

Botton, Fortz, Gouveia, Poss, 2013. Q. Botton, B. Fortz, L.E. Gouveia, M. PossBenders decomposition for the hop-constrained survivable network design problem, INFORMS Journal on Computing, 25 (1) (2013), pp. 13-26, 10.1287/ijoc.1110.0472

Bulajich Manfrino, Gómez Ortega, Valdez Delgado, 2009. R. Bulajich Manfrino, J.A. Gómez Ortega, R. Valdez DelgadoInequalities - A Mathematical Olympiad Approach, Birkhäuser Basel (2009)

R.S. de Camargo, G. de Miranda Jr., H.P.L. LunaBenders decomposition for hub location problems with economies of scale, Transportation Science, 43 (1) (2009), pp. 86-97

I. Contreras, J.-F. Cordeau, G. LaporteBenders. Decomposition for large-scale uncapacitated hub location, Operations Research, 59 (6) (2011), pp. 1477-1490, CrossRefView Record in Scopus

I. Contreras, E. Fernández, A. Marín Lagrangean. Bounds for the optimum communication spanning tree problem, TOP, 18 (1) (2010), pp. 140-157

I. Contreras, E. FernÁndez, A. MarÁnTight. Bounds from a path based formulation for the tree of hub location problem, Computers & Operations Research, 36 (12) (2009), pp. 3117-3127

I. Contreras, E. FernÁndez, A. MarÁnThe tree of hubs location problem, European Journal of Operational Research, 202 (2) (2010), pp. 390-400

J.-F. Cordeau, F. Soumis, J. Desrosiers. A Benders decomposition approach for the locomotive and car assignment problem, Transportation Science, 34 (2) (2000), pp. 133-149

J.-F. Cordeau, F. Soumis, J. Desrosiers. Simultaneous assignment of locomotives and cars to passenger trains, Operations Research, 49 (4) (2001), pp. 531-548

J.-F. Cordeau, G. Stojković, F. Soumis, J. Desrosiers. Benders decomposition for simultaneous aircraft routing and crew scheduling, Transportation Science, 35 (4) (2001), pp. 375-388

A.M. Costa. A survey on Benders decomposition applied to fixed-charge network design problems, Computers & Operations Research, 32 (6) (2005), pp. 1429-1450

A.M. Costa, J.-F. Cordeau, B. Gendron. Benders, metric and cutset inequalities for multicommodity capacitated network design, Computational Optimization and Applications, 42 (3) (2009), pp. 371-392, 10.1007/s10589-007-9122-0

J. Edmonds, R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the Association for Computing Machinery, 19 (2) (1972), pp. 248-264

E. FernÁndez, C. Luna-Mota, A. Hildenbrandt, G. Reinelt, S. Wiesberg. A flow formulation for the optimum communication spanning tree. Electronic Notes in Discrete Mathematics, 41 (Supplement C) (2013), pp. 85-92

T. Fischer, P. Merz. A memetic algorithm for the optimum communication spanning tree problem, Proceedings of the 4th international conference on hybrid metaheuristics. HM’07, Springer-Verlag, Berlin, Heidelberg (2007), pp. 170-184

M. Fischetti, G. Lancia, P. Serafini. Exact algorithms for minimum routing cost trees, Networks, 39 (3) (2002), pp. 161-173, 10.1002/net.10022

M. Fischetti, I. Ljubić, M. Sinn,l. Redesigning Benders decomposition for large-scale facility location, Management Science, 63 (7) (2017), pp. 2146-2162, 10.1287/mnsc.2016.2461

A.M. Geoffrion, G.W. Graves. Multicommodity distribution system design by Benders decomposition, Management Science, 26 (8) (1974), pp. 855-856

R.E. Gomory, T.C. Hu. Multi-terminal network flows, Journal of the Society for Industrial and Applied Mathematics, 9 (4) (1961), pp. 551-570

T.C. Hu. Optimum communication spanning trees, SIAM Journal on Computing, 3 (3) (1974), pp. 188-195

H. Kerivin, A.R. Mahjoub. Design of survivable networks: A survey, Networks, 46 (1) (2005), pp. 1-21, 10.1002/net.20072

J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7 (1) (1956), pp. 48-50

C. Luna-Mota. The Optimum Communication Spanning Tree Problem, Universitat Politècnica de Catalunya - Barcelona Tech (2015),Ph.D. dissertation

T.L. Magnanti, P. Mireault, R.T. WongTailoring Benders decomposition for uncapacitated network design. G. Gallo, C. Sandi (Eds.), Network flow at pisa, Mathematical Programming Studies, volume 26 (1986), pp. 112-154, 10.1007/BFb0121090

T.L. Magnanti, S. Raghavan. Strong formulations for network design problems with connectivity requirements, Networks, 45 (2) (2005), pp. 61-79, 10.1002/net.20046

T.L. Magnanti, L.A. Wolsey. Optimal Trees, Network models, Handbooks in Operations Research and Management Science, 7, Elsevier (1995), pp. 503-615

T.L. Magnanti, R.T. Wong. Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research, 29 (3) (1981), pp. 464-484

G. Mitra. Investigation of some branch and bound strategies for the solution of mixed integer linear programs, Mathematical Programming, 4 (1) (1973), pp. 155-170, 10.1007/BF01584658

J. Muckstadt, R. Wilson. An application of mixed-integer programming duality to scheduling thermal generating systems, Power Apparatus and Systems, IEEE Transactions on, PAS-87 (12) (1968), pp. 1968-1978, 10.1109/TPAS.1968.292156

Ortiz-Astorquiza, C., Contreras, I., & Laporte, G. (2018). An exact algorithm for multi-level uncapacitated facility location. Forthcoming in Transportation Science.

C. Palmer. Two algorithms for finding optimal communications spanning trees, Technical Report, Thomas J. Watson IBM Research Center (1994)

C.C. Palmer, A. Kershenbaum. An approach to a problem in network design using genetic algorithms, Networks, 26 (3) (1995), pp. 151-163

N. Papadakos. Practical enhancements to the Magnanti-Wong method, Operations Research Letters, 36 (4) (2008), pp. 444-449, 10.1016/j.orl.2008.01.005

N. Papadakos. Integrated airline scheduling, Computers & Operations Research, 36 (1) (2009), pp. 176-195, 10.1016/j.cor.2007.08.002 Part Special Issue: Operations Research Approaches for Disaster Recovery Planning

C.H. Papadimitriou, M. Yannakakis. Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, 43 (3) (1991), pp. 425-440

D. Peleg, E. Reshef. Deterministic polylog approximation for minimum communication spanning trees, K.G. Larsen, S. Skyum, G. Winskel (Eds.), Automata, languages and programming: 25th international colloquium, icalp’98 aalborg, denmark, july 13–17, 1998 proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg (1998), pp. 670-681

R.C. Prim. Shortest connection networks and some generalizations, The Bell System Technical Journal, 36 (6) (1957), pp. 1389-1401, 10.1002/j.1538-7305.1957.tb01515.x

C. Randazzo, H. Luna. A comparison of optimal methods for local access uncapacitated network design, Annals of Operations Research, 106 (1-4) (2001), pp. 263-286, 10.1023/A:1014569927266

F. Rothlauf. Design and applications of metaheuristics, Universitat Mannheim (2007)

F. Rothlauf. On optimal solutions for the optimal communication spanning tree problem, Operations Research, 57 (2) (2009), pp. 413-425, 10.1287/opre.1080.0592

F. Rothlauf, D.E. Goldberg. Representations for Genetic and Evolutionary Algorithms, Physica-Verlag (2002)

P. Sharma. Algorithms for the optimum communication spanning tree problem, Annals of Operations Research, 143 (1) (2006), pp. 203-209

S.-M. Soak. A new evolutionary approach for the optimal communication spanning tree problem., IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E89-A (10) (2006), pp. 2882-2893

C. Tilk, S. Irnich. Combined column-and-row-generation for the optimal communication spanning tree problem, Computers & Operations Research, 93 (2018), pp. 113-122

W.T. Tutte. On Hamiltonian circuits, Journal of the London Mathematical Society, s1-21 (2) (1946), pp. 98-101, 10.1112/jlms/s1-21.2.98

B.Y. Wu. A polynomial time approximation scheme for the two-source minimum routing cost spanning trees, Journal of Algorithms, 44 (2) (2002), pp. 359-378

B.Y. Wu, K.-M. Chao, C.Y. Tang. Approximation algorithms for some optimum communication spanning tree problems, Discrete Applied Mathematics, 102 (3) (2000), pp. 245-266

B.Y. Wu, K.-M. Chao, C.Y. Tang. A polynomial time approximation scheme for optimal product-requirement communication spanning trees, Journal of Algorithms, 36 (2) (2000), pp. 182-204

B.Y. Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, C.Y. Tang. A polynomial-time approximation scheme for minimum routing cost spanning trees, SIAM Journal on Computing, 29 (3) (2000), pp. 761-778

C.A. Zetina, I. Contreras, J.-F. Cordeau. Exact algorithms for the multicommodity uncapacitated fixed-charge network design problem,Technical Report (2017)
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top