Skip to main content
SpringerLink
Log in

Tabu search tutorial. A Graph Drawing Application

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Google Scholar 

  • Glover F (1989) Tabu search, Part I. ORSA J Comput 1(3):190–206

    Article  Google Scholar 

  • Glover F (1990) Tabu search, Part II. ORSA J Comput 2(1):4–32

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • Martí R (1998) A tabu search algorithm for the bipartite drawing problem. Eur J Oper Res 106:558–569

    Article  Google Scholar 

  • Martí R, Reinelt G (2011) The linear ordering problem. Exact and heuristic methods in combinatorial optimization. Springer, Heidelberg

    Book  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Xu J, Chiu S, Glover F (1997a) Tabu search for dynamic routing communications network design. Telecommun Syst 8:1–23

    Article  Google Scholar 

  • Xu J, Chiu S, Glover F (1997b) Probabilistic Tabu search for telecommunications network design. Comb Optim: Theory Pract 1(1):69–94

    Google Scholar 

  • 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

    Article  Google Scholar 

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

    Google Scholar 

  • 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

    Chapter  Google Scholar 

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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

Download references

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

  1. Meta-Analytics, Inc, Boulder, CO, USA

    Fred Glover

  2. Universitat de València, Valencia, Spain

    Vicente Campos & Rafael Martí

Authors
  1. Fred Glover
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vicente Campos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rafael Martí
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael Martí.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-021-00605-1

Keywords

Search

Navigation