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

Text (application/pdf)
882kBContreras 2018.pdf  Accepted Version Available under License Spectrum Terms of Access. 
Official URL: http://dx.doi.org/10.1016/j.ejor.2018.07.055
Abstract
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branchandcut framework a stronger reformulation of the problem, combinatorial lower bounds, intree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to stateoftheart 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 
Refereed:  Yes 
Authors:  Contreras, Ivan and Armando Zetina, Carlos and Fernández, Elena and LunaMota, Carlos 
Journal or Publication:  European Journal of Operational Research 
Date:  6 December 2017 
Funders: 

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 
References:
Achterberg, Koch, Martin, 2005. T. Achterberg, T. Koch, A. MartinBranching rules revisited, Operations Research Letters, 33 (1) (2005), pp. 4254, 10.1016/j.orl.2004.04.002Ahuja, Magnanti, Orlin, 1993. R.K. Ahuja, T.L. Magnanti, J.B. OrlinNetwork Flows: Theory, Algorithms, and Applications PrenticeHall, 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. 163170, 10.1287/trsc.21.3.163
BenAmeur, Neto, 2007. W. BenAmeur, J. NetoAcceleration of cutting plane and column generation algorithms: Applications to network design,Networks, 49 (1) (2007), pp. 317
Benders, 1962. J.F. BendersPartitioning procedures for solving mixedvariables programming problems. Numerische Mathematik, 4 (1962), pp. 238252
Botton, Fortz, Gouveia, Poss, 2013. Q. Botton, B. Fortz, L.E. Gouveia, M. PossBenders decomposition for the hopconstrained survivable network design problem, INFORMS Journal on Computing, 25 (1) (2013), pp. 1326, 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. 8697
I. Contreras, J.F. Cordeau, G. LaporteBenders. Decomposition for largescale uncapacitated hub location, Operations Research, 59 (6) (2011), pp. 14771490, 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. 140157
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. 31173127
I. Contreras, E. FernÁndez, A. MarÁnThe tree of hubs location problem, European Journal of Operational Research, 202 (2) (2010), pp. 390400
J.F. Cordeau, F. Soumis, J. Desrosiers. A Benders decomposition approach for the locomotive and car assignment problem, Transportation Science, 34 (2) (2000), pp. 133149
J.F. Cordeau, F. Soumis, J. Desrosiers. Simultaneous assignment of locomotives and cars to passenger trains, Operations Research, 49 (4) (2001), pp. 531548
J.F. Cordeau, G. Stojković, F. Soumis, J. Desrosiers. Benders decomposition for simultaneous aircraft routing and crew scheduling, Transportation Science, 35 (4) (2001), pp. 375388
A.M. Costa. A survey on Benders decomposition applied to fixedcharge network design problems, Computers & Operations Research, 32 (6) (2005), pp. 14291450
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. 371392, 10.1007/s1058900791220
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. 248264
E. FernÁndez, C. LunaMota, 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. 8592
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, SpringerVerlag, Berlin, Heidelberg (2007), pp. 170184
M. Fischetti, G. Lancia, P. Serafini. Exact algorithms for minimum routing cost trees, Networks, 39 (3) (2002), pp. 161173, 10.1002/net.10022
M. Fischetti, I. Ljubić, M. Sinn,l. Redesigning Benders decomposition for largescale facility location, Management Science, 63 (7) (2017), pp. 21462162, 10.1287/mnsc.2016.2461
A.M. Geoffrion, G.W. Graves. Multicommodity distribution system design by Benders decomposition, Management Science, 26 (8) (1974), pp. 855856
R.E. Gomory, T.C. Hu. Multiterminal network flows, Journal of the Society for Industrial and Applied Mathematics, 9 (4) (1961), pp. 551570
T.C. Hu. Optimum communication spanning trees, SIAM Journal on Computing, 3 (3) (1974), pp. 188195
H. Kerivin, A.R. Mahjoub. Design of survivable networks: A survey, Networks, 46 (1) (2005), pp. 121, 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. 4850
C. LunaMota. 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. 112154, 10.1007/BFb0121090
T.L. Magnanti, S. Raghavan. Strong formulations for network design problems with connectivity requirements, Networks, 45 (2) (2005), pp. 6179, 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. 503615
T.L. Magnanti, R.T. Wong. Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research, 29 (3) (1981), pp. 464484
G. Mitra. Investigation of some branch and bound strategies for the solution of mixed integer linear programs, Mathematical Programming, 4 (1) (1973), pp. 155170, 10.1007/BF01584658
J. Muckstadt, R. Wilson. An application of mixedinteger programming duality to scheduling thermal generating systems, Power Apparatus and Systems, IEEE Transactions on, PAS87 (12) (1968), pp. 19681978, 10.1109/TPAS.1968.292156
OrtizAstorquiza, C., Contreras, I., & Laporte, G. (2018). An exact algorithm for multilevel 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. 151163
N. Papadakos. Practical enhancements to the MagnantiWong method, Operations Research Letters, 36 (4) (2008), pp. 444449, 10.1016/j.orl.2008.01.005
N. Papadakos. Integrated airline scheduling, Computers & Operations Research, 36 (1) (2009), pp. 176195, 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. 425440
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. 670681
R.C. Prim. Shortest connection networks and some generalizations, The Bell System Technical Journal, 36 (6) (1957), pp. 13891401, 10.1002/j.15387305.1957.tb01515.x
C. Randazzo, H. Luna. A comparison of optimal methods for local access uncapacitated network design, Annals of Operations Research, 106 (14) (2001), pp. 263286, 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. 413425, 10.1287/opre.1080.0592
F. Rothlauf, D.E. Goldberg. Representations for Genetic and Evolutionary Algorithms, PhysicaVerlag (2002)
P. Sharma. Algorithms for the optimum communication spanning tree problem, Annals of Operations Research, 143 (1) (2006), pp. 203209
S.M. Soak. A new evolutionary approach for the optimal communication spanning tree problem., IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E89A (10) (2006), pp. 28822893
C. Tilk, S. Irnich. Combined columnandrowgeneration for the optimal communication spanning tree problem, Computers & Operations Research, 93 (2018), pp. 113122
W.T. Tutte. On Hamiltonian circuits, Journal of the London Mathematical Society, s121 (2) (1946), pp. 98101, 10.1112/jlms/s121.2.98
B.Y. Wu. A polynomial time approximation scheme for the twosource minimum routing cost spanning trees, Journal of Algorithms, 44 (2) (2002), pp. 359378
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. 245266
B.Y. Wu, K.M. Chao, C.Y. Tang. A polynomial time approximation scheme for optimal productrequirement communication spanning trees, Journal of Algorithms, 36 (2) (2000), pp. 182204
B.Y. Wu, G. Lancia, V. Bafna, K.M. Chao, R. Ravi, C.Y. Tang. A polynomialtime approximation scheme for minimum routing cost spanning trees, SIAM Journal on Computing, 29 (3) (2000), pp. 761778
C.A. Zetina, I. Contreras, J.F. Cordeau. Exact algorithms for the multicommodity uncapacitated fixedcharge network design problem,Technical Report (2017)
Repository Staff Only: item control page