As suggested by its title, the aim of this paper is to discuss how tabu search can be successfully applied to find high-quality solutions for a wide family of NP-hard optimization problems arising in a huge number of applied mathematics areas. The authors show that a graph drawing problem application is one of those excellent examples, given that since ever geometric representations play an important role in many real-world scenarios and are an important applied branch of graph theory.

This paper is divided in six sections. After an introductory section about the content of the article, a long section follows dedicated to a rich description of the tabu search scheme. The third section describes arc crossing and long arcs issues in graph theory and optimization. In Sect. 4, the authors describe the main ingredients of a tabu search for graph drawing and in Sect. 5 they report an extensive and critical analysis of the computational results they obtained in the comparison of the tabu search they designed with the state of the art techniques. Conclusions are drawn in the last section.

Section 2 exhaustively contains all the main characteristics of the tabu search metaheuristic framework. The term tabu search was coined by Fred Glover in 1986 (Glover 1986). Tabu search is a local search based multistart metaheuristic, whose main ingredients are listed in the following:

  • Development of sophisticated strategies that combine decision rules based on logical restructuring and non-monotonic search;

  • Possibility of violating solution feasibility and rules to restore it;

  • Flexible memory based on recency and frequency;

  • Robust rules for combining solutions, applied to a systematically maintained population.

Two nice articles published in ORSA Journal on Computing (Glover 1989, 1990) describe in detail the features mentioned above, not only from a formal point of view and discussing the robustness of the suboptimal solutions that their application is able to generate, but also and above all discussing the implementation details of the features themselves. Of particular interest in this section are the description of diversification and intensification stategies and the detailed description of the possible uses of memory typically made by tabu search algorithms: short-term memory and long-term memory; the latter details also widely discussed in the nice book by Glover and Laguna (1997).

In the third section, the authors provide a mathematical description of the class of arc crossing and long arcs problems. This type of problems is a quite interesting field involving researchers from heterogeneous education, such as Computer Science, Industrial Engineering, Mathematics, and Economics. The needed models for representing them have a combinatorial nature and analyzing these models one can use optimization tools (linear programming) or also heuristic approaches. The main problem treated in this section of the paper consists of optimally allign the nodes of a graph so to minimize the number of arc crossings. For dealing with this type of problems, the authors propose a sophisticated and robust tabu search algorithm.

Extensive computational experiments, on a significant set of test problems, have been carried out to empirically evaluate the performance of the proposed approach. The computational results show that the tabu search is effective in finding optimal or near optimal solutions in very limited computational time.

The paper concludes with an exhaustive list of references that helps who is interested to deepen the study of the topic to find the right sources to draw from.

In my opinion, this paper is what operations research is all about. Real problems are identified, modeled formally, analyzed theoretically and experimentally, and an alternative new unique framework to solve them is proposed and tested on benchmark instances. Furthermore, another important advantage of this article is that it can be read and understood not only by operations research experts, but also by university students who are now starting to study certain optimization issues.

If we really want to find a flaw in this manuscript, the section of the experiments could be improved by preparing the calculation of specific statistical meters and commenting on the values that they will assume after the measurement to be sure about the robustness of the proposed techniques. In particular, since for experimental evaluation of stochastic/randomized optimization algorithms it is obligatorily to repeat each experiment (algorithm execution with certain parameters on particular problem instance), in the paper it should be better highlighted information about the number of repetitions of runs for each problem instance. Moreover, the appropriate methodology requires that each experiment is repeated and some statistical value is reported. Traditionally, arithmetic mean was used for an indicator of performance, but this approach has some issues and median is more appropriate, in my opinion. Furthermore, if the authors wish, they could in addition report some other quantiles or some measure of variability and/or apply some ranked based methods. The authors could use ranking like in Friedman test and after that thay can use Friedman test with post hoc procedure to deal with family-wise error rate (FWER). Alternatively, they could skip post hoc and perform only Wilcoxon test (Wilcoxon 1945) for each pair.