Tabu search tutorial. A Graph Drawing Application

Fred Glover (), Vicente Campos () and Rafael Martí ()
Additional contact information
Fred Glover: Meta-Analytics, Inc
Vicente Campos: Universitat de València
Rafael Martí: Universitat de València

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2021, vol. 29, issue 2, No 1, 319-350

Abstract: 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.

Keywords: Tabu search; Metaheuristic; Graph drawing; Crossing minimization; Long edges (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11750-021-00605-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:29:y:2021:i:2:d:10.1007_s11750-021-00605-1

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-021-00605-1

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().