Tabu search tutorial. A Graph Drawing Application

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.