×

zbMATH — the first resource for mathematics

Comparison of metaheuristics for the \(k\)-labeled spanning forest problem. (English) Zbl 06744661
Summary: In this paper, we study the \(k\)-labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer-positive value \(\bar{k}\) are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound \(\bar {k}\) on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP-hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high-quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high-quality performance and completely automate the resulting optimization strategy.
MSC:
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Software:
GRASP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts , E. Korst , J. Michiels , W. 2005 Simulated annealing Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques 187 210
[2] Battiti, The LION Way: Machine Learning Plus Intelligent Optimization (2014)
[3] Battiti, Operations Research/Computer Science Interfaces Series (2008)
[4] Birattari, Tuning Metaheuristics: A Machine Learning Perspective (2009) · Zbl 1183.68464 · doi:10.1007/978-3-642-00483-4
[5] Blum, Hybrid metaheuristics, Computers & Operations Research 37 (3) pp 430– (2010) · Zbl 1173.90301 · doi:10.1016/j.cor.2009.03.002
[6] Blum, Hybrid metaheuristics in combinatorial optimization: a survey, Applied Soft Computing 11 (6) pp 4135– (2011) · Zbl 05920932 · doi:10.1016/j.asoc.2011.02.032
[7] Blum, Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Computing Surveys 35 (3) pp 268– (2003) · doi:10.1145/937503.937505
[8] Borne, Optimization in Engineering Sciences: Approximate and Metaheuristic Methods (2014)
[9] ggemann, Local search for the minimum label spanning tree problem with bounded colour classes, Operations Research Letters 31 pp 195– (2003) · Zbl 1046.90070 · doi:10.1016/S0167-6377(02)00241-9
[10] Brunato, Learning and intelligent optimization (LION): one ring to rule them all, Proceedings of the VLDB Endowment 6 (11) pp 1176– (2013) · doi:10.14778/2536222.2536247
[11] Carr , R.D. Doddi , S. Konjevod , G. Marathe , M. 2000 On the red-blue set cover problem Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms 345 353 · Zbl 0952.90026
[12] Carrabs, The labeled maximum matching problem, Computers & Operations Research 36 (6) pp 1859– (2009) · Zbl 1179.90318 · doi:10.1016/j.cor.2008.05.012
[13] Cerulli, The k-labeled spanning forest problem, Procedia-Social and Behavioral Sciences 108 pp 153– (2014) · doi:10.1016/j.sbspro.2013.12.828
[14] Cerulli, The Next Wave on Computing, Optimization, and Decision Technologies pp 93– (2005) · doi:10.1007/0-387-23529-9_7
[15] Cerulli, Extensions of the minimum labeling spanning tree problem, Journal of Telecommunications and Information Technology 4 pp 39– (2006)
[16] Chang, The minimum labeling spanning trees, Information Processing Letters 63 (5) pp 277– (1997) · Zbl 0938.90063 · doi:10.1016/S0020-0190(97)00127-0
[17] Chen, Telecommunications Modeling, Policy, and Technology. Vol. 44, Operations Research/Computer Science Interfaces pp 191– (2008)
[18] Consoli, Greedy randomized adaptive search and variable neighborhood search for the minimum labeling spanning tree problem, European Journal of Operational Research 196 (2) pp 440– (2009a) · Zbl 1163.90766 · doi:10.1016/j.ejor.2008.03.014
[19] Consoli, Variable neighborhood search for the minimum labeling Steiner tree problem, Annals of Operations Research 172 (1) pp 71– (2009b) · Zbl 1184.90134 · doi:10.1007/s10479-008-0507-y
[20] Consoli, Solving the minimum labeling spanning tree problem by intelligent optimization, Applied Soft Computing 28 pp 440– (2015) · doi:10.1016/j.asoc.2014.12.020
[21] Consoli, Proceedings of the Mini EURO Conference XXVIII on Variable Neighbourhood Search (EUROmC-XXVIII-VNS), Vol. 39 pp 75– (2012)
[22] Consoli, Proceedings of the 3rd International Conference on Variable Neighborhood Search (VNS’2014), Vol. 47 pp 29– (2015)
[23] Consoli, Nature Inspired Cooperative Strategies for Optimization, Vol. 129, Studies in Computational Intelligence pp 313– (2008)
[24] Consoli, Proceedings of the International Network Optimization Conference (INOC 2013), Vol. 41 pp 399– (2013)
[25] Demśar, Statistical comparison of classifiers over multiple data sets, Journal of Machine Learning Research 7 pp 1– (2006)
[26] Festa, An annotated bibliography of GRASP-part I: algorithms, International Transactions in Operational Research 16 (1) pp 1– (2009a) · Zbl 1153.90553 · doi:10.1111/j.1475-3995.2009.00663.x
[27] Festa, An annotated bibliography of GRASP-part I: applications, International Transactions in Operational Research 16 (2) pp 131– (2009b) · Zbl 1168.90582 · doi:10.1111/j.1475-3995.2009.00664.x
[28] Friedman, A comparison of alternative tests of significance for the problem of m rankings, Annals of Mathematical Statistics 11 pp 86– (1940) · JFM 66.1305.08 · doi:10.1214/aoms/1177731944
[29] Goldberg, Proceedings of the 4th International Conference on Genetic Algorithms pp 24– (1991)
[30] Hammadi, Multimodal Transport Systems (2013) · doi:10.1002/9781118577202
[31] Hansen, Variable neighborhood search, Computers and Operations Research 24 pp 1097– (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[32] Krumke, On the minimum label spanning tree problem, Information Processing Letters 66 (2) pp 81– (1998) · Zbl 0938.90064 · doi:10.1016/S0020-0190(98)00034-9
[33] Maniezzo, Matheuristics: Hybridizing Metaheuristics and Mathematical Programming (2010) · Zbl 1179.90007 · doi:10.1007/978-1-4419-1306-7
[34] Mascia, Learning and Intelligent Optimization. Lecture Notes in Computer Science pp 410– (2013) · doi:10.1007/978-3-642-44973-4_44
[35] Miller , J.S. 2006 Multimodal Statewide Transportation Planning: A Survey of State Practices Transportation Research Board, National Research Council, VA
[36] Nemenyi, Distribution-free multiple comparisons. Ph.D. thesis (1963)
[37] Pardalos, Handbook of Combinatorial Optimization (2nd edn) (2013) · Zbl 06135892 · doi:10.1007/978-1-4419-7997-1
[38] Silberholz, Comparison of heuristics for the colourful travelling salesman problem, International Journal of Metaheuristics 2 (2) pp 141– (2013) · Zbl 1306.90024 · doi:10.1504/IJMHEUR.2013.054143
[39] Stenger, An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping, Transportation Science 47 (1) pp 64– (2013) · doi:10.1287/trsc.1110.0396
[40] Tanenbaum, Computer Networks: Pearson New International Edition (2013)
[41] Triki, A theoretical study on the behavior of simulated annealing leading to a new cooling schedule, European Journal of Operational Research 166 (1) pp 77– (2005) · Zbl 1066.90043 · doi:10.1016/j.ejor.2004.03.035
[42] Voß, Looking ahead with the pilot method, Annals of Operations Research 136 pp 285– (2004) · Zbl 1114.90064 · doi:10.1007/s10479-005-2060-2
[43] Xiong, Improved heuristics for the minimum labeling spanning tree problem, IEEE Transactions on Evolutionary Computation 10 (6) pp 700– (2006) · Zbl 05516178 · doi:10.1109/TEVC.2006.877147
[44] Xiong, Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Vol. 37, Operations Research/Computer Science Interfaces Series pp 115– (2007) · Zbl 1241.90126 · doi:10.1007/978-0-387-48793-9_8
[45] Xiong, Telecommunications Modeling, Policy, and Technology, Vol. 44, Operations Research/Computer Science Interfaces pp 39– (2008)
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.