×

Tabu search tutorial. A graph drawing application. (English) Zbl 1474.90531

Summary: Tabu search is an optimization methodology that guides a local heuristic search procedure to explore the solution space beyond local optimality. It is substantiated by the hypothesis that an intelligent solving algorithm must incorporate memory to base its decisions on information collected during the search. The method creates in this way a learning pattern to explore the solution space economically and effectively. Tabu search is a metaheuristic that has proved its effectiveness in a wide variety of problems, especially in combinatorial optimization. We provide here a practical description of the methodology and apply it to a novel graph drawing problem. The most popular method of drawing graphs is the Sugiyama’s framework, which obtains a drawing of a general graph by transforming it into a proper hierarchy. In this way, the number of edge crossing is minimized in the first stage of the procedure. Many metaheuristics have been proposed to solve the crossing minimization problem within this drawing convention. The second stage of this procedure minimizes the number of bends of long arcs without increasing the number of crossings, thus obtaining a readable drawing. In this paper, we propose an alternative approach to simultaneously minimize the two criteria: crossing and long arc bends. We apply tabu search to solve this problem and compare its solutions with the optimal values obtained with CPLEX in small and medium-size instances.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization

Software:

Tabu search; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandes U, Köpf BA (2002) Fast and simple horizontal coordinate assignment. In: Mutzel P, Jünger M, Leipert S (eds) Graph drawing. Lecture Notes in Computer Science. Springer, Berlin, vol 2265, pp 31-44 · Zbl 1054.68569
[2] Carpano, M., Automatic display of hierarchized graphs for computer-aided decision analysis, IEEE Trans Syst Man Cybern, 10, 11, 705-715 (1980) · doi:10.1109/TSMC.1980.4308390
[3] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I., Graph drawing: algorithms for the visualization of graphs (1998), Upper Saddle River: Prentice Hall PTR, Upper Saddle River
[4] Glover F (1963) Parametric combinations of local job shop rules. Chapter IV, ONR Research Memorandum No. 117, GSIA, Carnegie-Mellon University, Pittsburgh
[5] Glover, F., Future paths for integer programming and links to artificial intelligence, Comput Oper Res, 13, 533, 549 (1986) · Zbl 0615.90083
[6] Glover, F., Tabu search, Part I, ORSA J Comput, 1, 3, 190-206 (1989) · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[7] Glover, F., Tabu search, Part II, ORSA J Comput, 2, 1, 4-32 (1990) · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[8] Glover, F.; Laguna, M.; Reeves, C., Tabu search, Chapter in modern heuristic techniques for combinatorial problems, 71-140 (1993), Oxford: Blackwell Scientific Publishing, Oxford
[9] Glover, F.; Laguna, M., Tabu search (1997), Boston: Kluwer Academic Publishers, Boston · Zbl 0930.90083 · doi:10.1007/978-1-4615-6089-0
[10] Glover, F.; Glover, R.; McMillan, C., A heuristic programming approach to the employee scheduling problem and some thoughts on managerial robots, J Oper Manag, 4, 2, 113-128 (1984) · doi:10.1016/0272-6963(84)90027-5
[11] Glover, F.; Hanafi, S.; Guermi, O.; Crevits, I., A simple multi-wave algorithm for the uncapacitated facility location problem, Front Eng Manag, 5, 451-465 (2018) · doi:10.15302/J-FEM-2018038
[12] Grötschel, M.; Michael Jünger, J.; Reinelt, G., A cutting plane algorithm for the linear ordering problem, Oper Res, 32, 6, 1195-1384 (1984) · Zbl 0554.90077 · doi:10.1287/opre.32.6.1195
[13] Guermi, O.; Nduwayoa, P.; Todosijevic, R.; Hanafi, S.; Glover, F., Probabilistic Tabu search for the cross-docking assignment problem, Eur J Oper Res, 277, 3, 875-885 (2019) · Zbl 1430.90377 · doi:10.1016/j.ejor.2019.03.030
[14] Jünger M, Lee EK, Mutzel P, Odenthal T (1997) A polyhedral approach to the multi-layer crossing minimization problem. In: International symposium on graph drawing. Springer, pp 13-24
[15] Jünger, M.; Mutzel, P., 2-layer straightline crossing minimization: performance of exact and heuristic algorithms, J Gr Algorithms Appl (1997) · Zbl 0906.05068 · doi:10.1142/9789812777638_0001
[16] Kaufmann M, Wagner D (2001) Drawing graphs: methods and models. Lecture Notes in Computer Science. Springer, Berlin · Zbl 0977.68644
[17] Laguna, M.; Martí, R., GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS J Comput, 11, 44-52 (1999) · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44
[18] Løkketangen, A.; Glover, F.; Osman, IH; Kelly, JP, Probabilistic move selection in Tabu search for zero-one mixed integer programming problems, Meta-heuristics: theory & applications, 467-487 (1996), Berlin: Springer, Berlin · Zbl 0877.90058 · doi:10.1007/978-1-4613-1361-8_28
[19] Martí, R., A tabu search algorithm for the bipartite drawing problem, Eur J Oper Res, 106, 558-569 (1998) · Zbl 0991.90128 · doi:10.1016/S0377-2217(97)00291-9
[20] Martí, R.; Reinelt, G., The linear ordering problem. Exact and heuristic methods in combinatorial optimization (2011), Heidelberg: Springer, Heidelberg · Zbl 1213.90005 · doi:10.1007/978-3-642-16729-4
[21] Martí, R.; Campos, V.; Hoff, A.; Peiró, J., Heuristics for the min-max arc crossing problem in graphs, Expert Syst Appl, 109, 100-113 (2018) · doi:10.1016/j.eswa.2018.05.008
[22] Napoletano, A.; Martínez-Gavara, A.; Festa, P.; Pastore, T.; Martí, R., Tabu search for min-max edge crossings in graphs, Eur J Oper Res, 274, 710-729 (2019) · Zbl 1404.90141 · doi:10.1016/j.ejor.2018.10.017
[23] North SC (1996) Incremental layout in DynaDAG. In: Proceedings of Graph Drawing’95. Lecture Notes in Computer Science, vol 1027, pp 409-418. Springer, Berlin
[24] Pastore, T.; Martínez-Gavara, A.; Napoletano, A.; Festa, P.; Martí, R., Heuristics for the constrained incremental graph drawing problem, Comput Oper Res, 114, 104830 (2020) · Zbl 1458.90621 · doi:10.1016/j.cor.2019.104830
[25] Sánchez-Oro, J.; Martínez-Gavara, A.; Laguna, M.; Martí, R.; Duarte, A., Variable neighborhood scatter search for the incremental graph drawing problem, Comput Optim Appl, 68, 775-797 (2017) · Zbl 1386.05122 · doi:10.1007/s10589-017-9926-5
[26] Shang Z, Hao J-K, Zhao S, Wang Y (2021) Multi-wave tabu search for the boolean quadratic programming problem with generalized upper bound constraints. In: IFORS 2021, the 22nd conference of the International Federation of Operational Research Societies
[27] Sugiyama, K.; Tagawa, S.; Toda, M., Methods for visual understanding of hierarchical system structures, IEEE Trans Syst Man Cybern SMC, 11, 2, 109-125 (1981) · doi:10.1109/TSMC.1981.4308636
[28] Wu, Q.; Hao, J-K; Glover, F., Multi-neighborhood tabu search for the maximum weight clique problem, Ann Oper Res, 196, 1, 611-634 (2013) · Zbl 1251.90378 · doi:10.1007/s10479-012-1124-3
[29] Xu, J.; Chiu, S.; Glover, F., Using Tabu search to solve the Steiner tree-star problem in telecommunications network design, Telecommunications Systems, 6, 117-125 (1996) · doi:10.1007/BF02114289
[30] Xu, J.; Chiu, S.; Glover, F., Tabu search for dynamic routing communications network design, Telecommun Syst, 8, 1-23 (1997) · doi:10.1023/A:1019149101850
[31] Xu, J.; Chiu, S.; Glover, F., Probabilistic Tabu search for telecommunications network design, Comb Optim: Theory Pract, 1, 1, 69-94 (1997)
[32] Yagiura, M.; Iwasaki, S.; Ibaraki, T.; Glover, F., A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Discret Optim, 1, 87-98 (2004) · Zbl 1087.90043 · doi:10.1016/j.disopt.2004.03.005
[33] Glover, F.; Barr, RS; Helgason, RV; Kennington, JL, Tabu search and adaptive memory programming—advances, applications and challenges, Interfaces in computer science and operations research, 1-75 (1997), Boston: Kluwer Academic Publishers, Boston · Zbl 0882.90111
[34] Glover, F.; Laguna, M.; Pardalos, PM; Du, D-Z; Graham, RL, Tabu Search in Analytics and Computational Science, Handbook of Combinatorial Optimization, 3261-3362 (2013), Norwell: Kluwer Academic Publishers, Norwell · doi:10.1007/978-1-4419-7997-1_17
[35] Barr, R.; Glover, F.; Huskinson, T.; Kochenberger, G., An extreme-point Tabu-search algorithm for fixed charge network problems, Netw Int J: Spec Issue Celebr 50 Years Netw: Part 2, 77, 2, 322-340 (2020)
[36] Glover, F.; Hanafi, S.; Guermi, O.; Crevits, I., A simple multi-wave algorithm for the uncapacitated facility location problem, Front Eng Manag, 5, 4, 451-465 (2018) · doi:10.15302/J-FEM-2018038
[37] Lai, X.; Hao, J-K; Lü, Z.; Glover, F., A learning-based path relinking algorithm for the bandwidth coloring problem, Eng Appl Artif Intell, 52, 81-91 (2016) · doi:10.1016/j.engappai.2016.02.008
[38] Lai, X.; Hao, J-K; Glover, F.; Lü, Z., A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem, Inf Sci, 436-437, 282-301 (2018) · Zbl 1440.90062 · doi:10.1016/j.ins.2018.01.026
[39] Lai, X.; Hao, J-K; Glover, F.; Yue, D., Intensification-driven tabu search for the minimum differential dispersion problem, Knowl-Based Syst, 167, 1, 168-186 (2019)
[40] Lai, X.; Hao, J-K; Glover, F., A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem, Expert Syst Appl, 139, 112856 (2020) · doi:10.1016/j.eswa.2019.112856
[41] Lai, X.; Yuea, D.; Hao, J-K; Glover, F., Solution-based tabu search for the maximum min-sum dispersion problem, Inf Sci, 441, 79-94 (2018) · doi:10.1016/j.ins.2018.02.006
[42] Wang, Y.; Hao, J-K; Glover, F.; Lu, Z., A Tabu search based memetic algorithm for the maximum diversity problem, Eng Appl Artif Intell, 27, 103-114 (2014) · doi:10.1016/j.engappai.2013.09.005
[43] Yagiura, M.; Ibaraki, T.; Glover, F., A path relinking approach with ejection chains for the generalized assignment problem, Eur J Oper Res, 169, 548-569 (2006) · Zbl 1079.90119 · doi:10.1016/j.ejor.2004.08.015
[44] Yagiura M, Komiya A, Kojima K, Nonobe K, Nagamochi H, Ibaraki T, Glover F (2007) A path relinking approach for the multi-resource generalized quadratic assignment problem. Lecture Notes in Computer Science. Springer, Berlin, vol 4638, pp 121-135 · Zbl 1134.68500
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.