×

zbMATH — the first resource for mathematics

Empirical study of exact algorithms for the multi-objective spanning tree. (English) Zbl 1432.90153
Summary: The multi-objective spanning tree (MoST) is an extension of the minimum spanning tree problem (MST) that, as well as its single-objective counterpart, arises in several practical applications. However, unlike the MST, for which there are polynomial-time algorithms that solve it, the MoST is NP-hard. Several researchers proposed techniques to solve the MoST, each of those methods with specific potentialities and limitations. In this study, we examine those methods and divide them into two categories regarding their outcomes: Pareto optimal sets and Pareto optimal fronts. To compare the techniques from the two groups, we investigated their behavior on 2, 3 and 4-objective instances from different classes. We report the results of a computational experiment on 8100 complete and grid graphs in which we analyze specific features of each algorithm as well as the computational effort required to solve the instances.
MSC:
90C35 Programming involving graphs or networks
90C29 Multi-objective and goal programming
Software:
LEDA; VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aggarwal, V.; Aneja, Y.; Nair, K., Minimal spanning tree subject to a side constraint, Comput. Oper. Res., 9, 287-296 (1982)
[2] Alonso, S.; Domínguez-Ríos, Ma; Colebrook, M.; Sedeño-Noda, A., Optimality conditions in preference-based spanning tree problems, Eur. J. Oper. Res., 198, 232-240 (2009) · Zbl 1163.90791
[3] Andersen, Ka; Jörnsten, K.; Lind, M., On bicriterion minimal spanning trees: an approximation, Comput. Oper. Res., 23, 12, 1171-1182 (1996) · Zbl 0876.90087
[4] Arroyo, Jec; Vieira, Ps; Vianna, Ds, A GRASP algorithm for the multi-criteria minimum spanning tree problem, Ann. Oper. Res., 159, 125-133 (2008) · Zbl 1155.90446
[5] Barrow, Jd; Bhavsar, Sp; Sonoda, Dh, Minimal spanning trees, filaments and galaxy clustering, Mon. Not. R. Astron. Soc., 216, 1, 17-35 (1985)
[6] Bazlamaçci, Cf; Hindi, Ks, Minimum-weight spanning tree algorithms a survey and empirical study, Comput. Oper. Res., 28, 8, 767-785 (2001) · Zbl 1018.90062
[7] Chen, G.; Chen, S.; Guo, W.; Chen, H., The multi-criteria minimum spanning tree problem based genetic algorithm, Inf. Sci., 117, 22, 5050-5063 (2007) · Zbl 1121.90127
[8] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Math. Program., 20, 1, 255-282 (1981) · Zbl 0461.90067
[9] Climaco, Jc; Pascoal, Mmb, Multicriteria path and tree problems: discussion on exact algorithms and applications, Int. Trans. Oper. Res., 19, 63-98 (2012) · Zbl 1267.90022
[10] Corley, Hw, Efficient spanning trees, J. Optim. Theory Appl., 45, 3, 481-485 (1985) · Zbl 0544.05052
[11] Davis-Moradkhan, M., Browne, W. N., Grindrod, P.: Extending evolutionary algorithms to discover tri-criterion and non-supported solutions for the minimum spanning tree problem. In: GECCO ’09—Genetic and Evolutionary Computational Conference, 2009, Montréal. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (GECCO ’09), pp. 1829-1830 (2009)
[12] Davis-Moradkhan, M., Browne, W.N.: A knowledge-based evolution strategy for the multi-objective minimum spanning tree problem. In: IEEE Congress on Evolutionary Computation, 2006. CEC 2006, pp. 1391-1398 (2006)
[13] Davis-Moradkhan, M., Multi-criterion optimization in minimum spanning trees, Stud. Inform. Univers., 8, 185-208 (2010)
[14] Dias, J., Sovereign debt crisis in the European Union: a minimum spanning tree approach, Physica A, 391, 5, 2046-2055 (2012)
[15] Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum, 22, 425-460 (2000) · Zbl 1017.90096
[16] Eom, C.; Kwon, O.; Jung, Ws; Kim, S., The effect of a market factor on information flow between stocks using the minimal spanning tree, Physica A, 389, 8, 1643-1652 (2010)
[17] Galand, L.; Perny, P.; Spanjaard, O., Choquet-based optimisation in multiobjective shortest path and spanning tree problem, Eur. J. Oper. Res., 204, 303-315 (2010) · Zbl 1178.90333
[18] Garey, Mr; Johnson, Ds, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco: W. H. Freeman, San Francisco
[19] Grönlund, A.; Bhalerao, Rp; Karlsson, J., Modular gene expression in Poplar: a multilayer network approach, New Phytol., 181, 2, 315-322 (2009)
[20] Hamacher, Hw; Ruhe, G., On spanning tree problems with multiple objectives, Ann. Oper. Res., 52, 209-230 (1994) · Zbl 0821.90126
[21] Jothi, R.; Raghavachari, B., Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design, ACM Trans. Algorithms, 1, 2, 265-282 (2005) · Zbl 1321.68386
[22] Knowles, Jd; Corne, Dw, Enumeration of Pareto optimal multi-criteria spanning trees—a proof of the incorrectness of Zhou and Gen’s proposed algorithm, Eur. J. Oper. Res., 143, 3, 543-547 (2002) · Zbl 1082.90560
[23] Knowles, J.D., Corne, D.W.: Benchmark problem generators and results for the multiobjective degree-constrained minimum spanning tree problem. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 424-431 (2001)
[24] Kruskal, Jb, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 7, 48-50 (1956) · Zbl 0070.18404
[25] Lokman, B.; Köksalan, M., Finding all nondominated points of multi-objective integer programs, J. Global Optim., 57, 2, 347-365 (2013) · Zbl 1315.90008
[26] Luo, J., Zhang, X.: New method for constructing phylogenetic tree based on 3D graphical representation. In: ICBBE 2007 The 1st International Conference on Bioinformatics and Biomedical Engineering, pp. 318-321 (2007)
[27] Magnanti, Tl; Wong, Rt, Network design and transportation planning: models and algorithms, Transp. Sci., 18, 1, 1-55 (1984)
[28] Melhorn, K.; Näher, S., LEDA: A Platform for Combinatorial and Geometric Computing (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0976.68156
[29] Monteiro, S.M.D., Goldbarg, E.F.G., Goldbarg, M.C.: A plasmid based transgenetic algorithm for the biobjective minimum spanning tree problem. In: EVOCOP09—European Conference on Evolutionary Computation in Combinatorial Optimization, 2009, Tübingen. Lecture Notes in Computer Science, vol. 5482, pp. 49-60 (2009)
[30] Monteiro, S.M.D., Goldbarg, E.F.G., Goldbarg, M.C.: A new transgenetic approach for the biobjective spanning tree problem. In: IEEE CEC 2010 Congress on Evolutionary Computation, 2010, Barcelona. Proceedings of IEEE CEC 2010 Congress on Evolutionary Computation, vol. 1, pp 519-526 (2010)
[31] Paquete, L.; Chiarandini, M.; Stützle, T.; Gandibleux, X.; Sevaux, M.; Sörensen, K.; T’Kindt, V., Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study, Metaheuristics for Multiobjective Optimisation, 177-200 (2004), Berlin: Springer, Berlin
[32] Paquete, L.; Stützle, T., A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices, Eur. J. Oper. Res., 169, 943-959 (2006) · Zbl 1079.90113
[33] Perny, P.; Spanjaard, O., A preference-based approach to spanning trees and shortest paths problems, Eur. J. Oper. Res., 165, 584-601 (2005) · Zbl 1065.90064
[34] Prim, Rc, Shortest connection networks and some generalizations, Bell Syst. Tech. J., 36, 1389-1401 (1957)
[35] Pugliese, Lp; Guerriero, F.; Santos, Jl, Dynamic programming for spanning tree problems: application to the multi-objective case, Optim. Lett., 9, 437-450 (2015) · Zbl 1317.90312
[36] Ramos, Rm; Alonso, S.; Sicilia, J.; González, C., The problem of the optimal biobjective spanning tree, Eur. J. Oper. Res., 111, 3, 617-628 (1998) · Zbl 0937.90112
[37] Rocha, D.A.M., Goldbarg, E.F.G., Goldbarg, M.C.: A memetic algorithm for the biobjective minimum spanning tree problem. In: 6th European Conference on Evolutionary Computation in Combinatorial Optimization, Budapest, Lecture Notes in Computer Science, vol. 3906, pp 222-233 (2006)
[38] Rocha, D.A.M., Goldbarg, E.F.G., Goldbarg, M.C.: A new evolutionary algorithm for the bi-objective minimum spanning tree. In: ISDA’07 Seventh International Conference on Intelligent Systems Design and Applications, 2007, Rio de Janeiro. Proceedings of ISDA’07, vol. 1, pp. 735-740 (2007)
[39] Ruzika, S.; Hamacher, Hw; Lerner, J.; Wagner, D.; Zweig, Ka, A survey on multiple objective minimum spanning tree problems, Algorithmics of Large and Complex Networks, 104-116 (2009), Berlin: Springer, Berlin · Zbl 1248.68388
[40] Santos, Jl; Pugliese, Lp; Guerriero, F., A new approach for the multiobjective minimum spanning tree, Comput. Oper. Res., 98, 69-83 (2018) · Zbl 1391.90618
[41] Sörensen, K.; Janssens, Gk, An algorithm to generate all spanning trees of a graph in order of increasing cost, Pesquisa Operacional, 25, 2, 219-229 (2005)
[42] Sourd, F.; Spanjaard, O., A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem, INFORMS J. Comput., 20, 3, 472-484 (2008) · Zbl 1243.90206
[43] Steiner, S.; Radzik, T., Computing all efficient solutions of the biobjective minimum spanning tree problem, Comput. Oper. Res., 35, 1, 198-211 (2008) · Zbl 1149.90403
[44] Sylva, J.; Crema, A., A method for finding the set of non-dominated vectors for multiple objective integer linear programs, Eur. J. Oper. Res., 158, 1, 46-55 (2004) · Zbl 1061.90103
[45] Talbi, Eg; Basseur, M.; Nebro, Aj; Alba, E., Multi-objective optimization using metaheuristics: non-standard algorithms, Int. Trans. Oper. Res., 19, 1-2, 283-305 (2012) · Zbl 1270.90067
[46] Tewarie, P.; Hillebrand, A.; Schoonheim, Mm; Van Dijk, Bw; Geurts, Jjg; Barkhof, F.; Polman, Ch; Stam, Cj, Functional brain network analysis using minimum spanning trees in Multiple Sclerosis: an MEG source-space study, Neuroimage, 88, 308-318 (2014)
[47] Van Dellen, E.; Douw, L.; Hillebrand, A.; De Witt Hamer, Pc; Baayen, Jc; Heimans, Jj; Reijneveld, Jc; Stam, Cj, Epilepsy surgery outcome and functional network alterations in longitudinal MEG: a minimum spanning tree analysis, Neuroimage, 86, 354-363 (2014)
[48] Waxman, Bm, Routing of multipoint connections, IEEE J. Sel. Areas Commun., 6, 9, 1617-1622 (1988)
[49] Zhou, G.; Gen, M., Genetic algorithm approach on multi-criteria minimum spanning tree problem, Eur. J. Oper. Res., 114, 141-152 (1999) · Zbl 0945.90009
[50] Zhou, A.; Qu, B-Y; Li, H.; Zhao, S-Z; Suganthan, Pn; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evolut. Comput., 1, 32-49 (2011)
[51] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (1999)
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.