Abstract
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.
Similar content being viewed by others
References
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
Carpano M (1980) Automatic display of hierarchized graphs for computer-aided decision analysis. IEEE Trans Syst Man Cybern 10(11):705–715
Di Battista G, Eades P, Tamassia R, Tollis I (1998) Graph drawing: algorithms for the visualization of graphs, 1st edn. Prentice Hall PTR, Upper Saddle River
Glover F (1963) Parametric combinations of local job shop rules. Chapter IV, ONR Research Memorandum No. 117, GSIA, Carnegie-Mellon University, Pittsburgh
Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(533):549
Glover F (1989) Tabu search, Part I. ORSA J Comput 1(3):190–206
Glover F (1990) Tabu search, Part II. ORSA J Comput 2(1):4–32
Glover F, Laguna M (1993) Tabu search. In: Reeves C (ed) Chapter in modern heuristic techniques for combinatorial problems. Blackwell Scientific Publishing, Oxford, pp 71–140
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston
Glover F, Glover R, McMillan C (1984) A heuristic programming approach to the employee scheduling problem and some thoughts on managerial robots. J Oper Manag 4(2):113–128
Glover F, Hanafi S, Guermi O, Crevits I (2018a) A simple multi-wave algorithm for the uncapacitated facility location problem. Front Eng Manag 5:451–465
Grötschel M, Michael Jünger J, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Oper Res 32(6):1195–1384
Guermi O, Nduwayoa P, Todosijevic R, Hanafi S, Glover F (2019) Probabilistic Tabu search for the cross-docking assignment problem. Eur J Oper Res 277(3):875–885
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
Jünger M, Mutzel P (1997) 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J Gr Algorithms Appl. https://doi.org/10.1142/9789812777638_0001
Kaufmann M, Wagner D (2001) Drawing graphs: methods and models. Lecture Notes in Computer Science. Springer, Berlin
Laguna M, Martí R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44–52
Løkketangen A, Glover F (1996) Probabilistic move selection in Tabu search for zero-one mixed integer programming problems. In: Osman IH, Kelly JP (eds) Meta-heuristics: theory & applications. Springer, Berlin, pp 467–487
Martí R (1998) A tabu search algorithm for the bipartite drawing problem. Eur J Oper Res 106:558–569
Martí R, Reinelt G (2011) The linear ordering problem. Exact and heuristic methods in combinatorial optimization. Springer, Heidelberg
Martí R, Campos V, Hoff A, Peiró J (2018) Heuristics for the min-max arc crossing problem in graphs. Expert Syst Appl 109:100–113
Napoletano A, Martínez-Gavara A, Festa P, Pastore T, Martí R (2019) Tabu search for min-max edge crossings in graphs. Eur J Oper Res 274:710–729
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
Pastore T, Martínez-Gavara A, Napoletano A, Festa P, Martí R (2020) Heuristics for the constrained incremental graph drawing problem. Comput Oper Res 114:104830
Sánchez-Oro J, Martínez-Gavara A, Laguna M, Martí R, Duarte A (2017) Variable neighborhood scatter search for the incremental graph drawing problem. Comput Optim Appl 68:775–797
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
Sugiyama K, Tagawa S, Toda M (1981) Methods for visual understanding of hierarchical system structures. IEEE Trans Syst Man Cybern SMC 11(2):109–125
Wu Q, Hao J-K, Glover F (2013) Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res 196(1):611–634
Xu J, Chiu S, Glover F (1996) Using Tabu search to solve the Steiner tree-star problem in telecommunications network design. Telecommunications Systems 6:117–125
Xu J, Chiu S, Glover F (1997a) Tabu search for dynamic routing communications network design. Telecommun Syst 8:1–23
Xu J, Chiu S, Glover F (1997b) Probabilistic Tabu search for telecommunications network design. Comb Optim: Theory Pract 1(1):69–94
Yagiura M, Iwasaki S, Ibaraki T, Glover F (2004) A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem. Discret Optim 1:87–98
Additional selected references: fundamental papers
Glover F (1997) Tabu search and adaptive memory programming—advances, applications and challenges. In: Barr RS, Helgason RV, Kennington JL (eds) Interfaces in computer science and operations research. Kluwer Academic Publishers, Boston, pp 1–75
Glover F, Laguna M (2013) Tabu Search in Analytics and Computational Science. In: Pardalos PM, Du D-Z, Graham RL (eds) Handbook of Combinatorial Optimization, vol XXI, 2nd edn. Kluwer Academic Publishers, Norwell, pp 3261–3362
A sampling of studies establishing new records
Barr R, Glover F, Huskinson T, Kochenberger G (2020) 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
Glover F, Hanafi S, Guermi O, Crevits I (2018b) A simple multi-wave algorithm for the uncapacitated facility location problem. Front Eng Manag 5(4):451–465
Lai X, Hao J-K, Lü Z, Glover F (2016) A learning-based path relinking algorithm for the bandwidth coloring problem. Eng Appl Artif Intell 52:81–91
Lai X, Hao J-K, Glover F, Lü Z (2018a) A two-phase tabu-evolutionary algorithm for the 0–1 multidimensional knapsack problem. Inf Sci 436–437:282–301
Lai X, Hao J-K, Glover F, Yue D (2019) Intensification-driven tabu search for the minimum differential dispersion problem. Knowl-Based Syst 167(1):168–186
Lai X, Hao J-K, Glover F (2020) A study of two evolutionary/tabu search approaches for the generalized max-mean dispersion problem. Expert Syst Appl 139:112856
Lai X, Yuea D, Hao J-K, Glover F (2018b) Solution-based tabu search for the maximum min-sum dispersion problem. Inf Sci 441:79–94
Wang Y, Hao J-K, Glover F, Lu Z (2014) A Tabu search based memetic algorithm for the maximum diversity problem. Eng Appl Artif Intell 27:103–114
Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur J Oper Res 169:548–569
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
Acknowledgements
This research has been partially supported by the Spanish Government, Ministerio de Ciencia, Innovación y Universidades, with Grant Ref. PGC2018-0953322-B-C21/MCIU/AEI/FEDER-UE.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This invited paper is discussed in the comments available at: https://doi.org/10.1007/s11750-021-00606-0, https://doi.org/10.1007/s11750-021-00607-z, https://doi.org/10.1007/s11750-021-00608-y.
Rights and permissions
About this article
Cite this article
Glover, F., Campos, V. & Martí, R. Tabu search tutorial. A Graph Drawing Application. TOP 29, 319–350 (2021). https://doi.org/10.1007/s11750-021-00605-1
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-021-00605-1