Note from the Editor

We continue to announce the winners of INFORMS Journal on Computing (IJOC) Test of Time Paper Award to cover the backlog of awards since the journal’s inception. The energetic and able committee chaired by John Chinneck with members Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff has selected the awardee, covering the period 1992 through 1996. What follows is the citation from the award committee and then a reflective interview with the authors about this paper.

I want to thank the committee for their superb efforts and am very pleased to share this recognition of the impactful heritage of our journal.

All my best,

The Test of Time Award for papers published in the INFORMS Journal on Computing in the years 1992–1996 is awarded to

The Reactive Tabu Search

Roberto Battiti and Giampiero Tecchiolli

ORSA Journal on Computing 6(2):126–140, 1994

https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.6.2.126

Test of Time Award Citation 1992–1996

This paper describes the new reactive tabu search (RTS), which augments the basic tabu search technique with a check for the repetition of configurations. The method learns the best length for the tabu list by reacting to detected cycles and includes a careful computational study of schemes for managing memory and list search time. These were important improvements to the basic tabu search algorithm. The paper is frequently cited to this day and has influenced work in maxSAT, ant colony optimization, and many others. The algorithm has been used in many applications, including vehicle routing, job shop scheduling, etc.

Retrospective Interview with the Authors, Roberto Battiti and Giampiero Tecchiolli

Your Paper Presents Only the Final Results, so Can You Share How You Developed the Seminal Ideas About Reactive Tabu Search?

Roberto: The intuition emerged in the late ‘80 s while I was studying for my Ph.D. at Caltech (California Institute of Technology) before joining the faculty of the University of Trento. At those times, simulated annealing [SA] was generating hype about a general-purpose solver for complex optimization tasks. The recipe was simple: start from local (perturbative) search. To avoid local minima traps, add a probabilistic rule for accepting also worsening moves, depending on a “temperature” parameter, which is gradually reduced. Fast forward to infinite time and observe the state of the system; it will be at a global optimum with probability tending to one.

The beauty of SA is reflected by its asymptotic convergence theorems (let time tend to infinity to identify the optimal solution) and by its analogy with the annealing process of metals in physics. But nobody lives long enough to experience infinite time. Statistical mechanics teaches us that having your table jumping up one foot spontaneously for a lucky movement of atoms has a probability greater than zero, but the probability is so low and our lives so limited that we will never observe it in practice. Of course, researchers knew that we could not wait for infinite time and proposed heuristic variations of SA. What we found inappropriate from an epistemological point of view was to “cover one’s shoulders” with asymptotic results, feeling empowered by these results to apply heuristics. It looked like marketing to us, not science. SA is memoryless, and memory (learning from the past) is so powerful…

Giampietro: In the early ‘90 s, I was a researcher at IRST (Istituto per la Ricerca Scientifica e Tecnologica), an ambitious public organization at Trento (Italy) that pioneered a holistic approach to artificial intelligence and microelectronics. My activities addressed the most common issues of training neural networks based on backpropagation. Backprop is slow to converge and lacks a global optimization approach. It is ultimately based on a gradient descent through an endless sequence of small steps—a problem that is currently addressed by brute force massive computational resources (leading to monstrous profits for Nvidia). If we consider the biological counterpart of artificial neural nets, they are significantly different and more energy efficient. Learning in commercial deep neural nets, like ChatGPT, requires the energy of a nuclear power plant, while some pizzas are sufficient for a kid’s brain. Our brain is much more efficient but not as precise and accurate as a modern computer. This fact inspired many researchers to use a more “biological-inspired” approach to building artificial neural nets (see, for example, the Intel ETANN processor based on analog computation blocks that was introduced in the market around 1989) (Holler et al. 1989), where the computational overhead is much lower, but backprop cannot be used for training.

After the Initial Insight About “Learning on the Job” for Optimization, Why Did You Focus on Tabu Search?

Giampietro: While considering derivative-free algorithms for training (based only on function evaluations), I was inspired by tabu search because of its search strategy in which a set of simple moves is used to explore the search space, while the steps back are forbidden for a while—a sort of intelligent “try and go” process in which the actions are remembered for a while to avoid the repetition of the sequences already applied. This is very similar to what humans do to solve a new problem. Real creativity requires staying away from known solutions or “pet” hypotheses (prohibiting known local optima).

My collaboration with Roberto started here and stimulated a very exciting and prolific period of my professional life that resulted, among other things, in the idea of the reactive tabu search algorithm. In the RTS algorithm, starting from the human memory–based way to solve unknown search problems, we added new ingredients to tabu search to make it even more “intelligent”: the ability to tune the prohibition period based on the local properties of the search space and the ability to detect chaotic attractors that could trap forever the search trajectory. If we are searching in a flat landscape, we go fast and far, but if we are on rugged terrain with a harsh face marked by cavernous furrows and rough ridges, we tend to stumble and be trapped by deep local minima. These ingredients introduced in the tabu search a better and automated balance between intensification and diversification, thus making it possible to find good solutions with a lower average computational effort.

Roberto: The points about simulated annealing were (i) asymptotic results are irrelevant for practical optimization; (ii) asymptotic results tend to be trivial in a memoryless (Markov) system—even a blind algorithm like pure random search has them; (iii) if one is interested in asymptotics, then exhaustive enumeration (in the case of discrete systems) converges in finite time—exponential but still less than infinity.

I was lucky to meet Giampietro and spend long days of joint creativity without any money or formal projects. Forgetting about what happened in the previous phase of the heuristic search appeared to us as contrary to what should be done, i.e., to use all data produced during the past search to learn to search better in the next steps. If a local minimum is a light in the night attracting insects, we visualized SA’s trajectory as a moth circling it for endless time. No kids would do that because they have quick on-the-job learning abilities—not by genetics, but because their brains keep modifying connections while getting fresh data from experience. A seminal paper using memory as part of the heuristic was one by Fred Glover about tabu search, and this is why we decided to submit our work to the ORSA Journal.

Learning to search is related to tuning (and self-tuning) of meta-parameters of the algorithm; to increasing the level of automation and, therefore, the reach and power of optimization; to ensure reproducibility by making self-tuning an integral part of the algorithm, not depending on the individual brains of the researcher.

What Happened Next?

Roberto: It has been 30 years ago; fast-forward to now, reactive tabu search led to reactive search and intelligent optimization (Battiti et al. 2008), which led to a much wider plan to use machine learning as an integral part of optimization heuristics (LION—machine learning and intelligent optimization), a field which is booming now (see also LION Conference 2024). The strong interconnection between machine learning and optimization is now widely recognized and rediscovered from time to time.

Giampietro: We applied RTS to many problems, and with Roberto, we could apply it successfully to the neural nets training problem (Battiti and Tecchiolli 1995), and that has given me the chance to achieve my initial goal. RTS also demonstrated that digital neuromorphic chips could be built without using analog computation (Lee et al. 1995). I’m still using it in my professional life with very satisfactory results.

Any Advice for Early Career Researchers?

Roberto and Giampietro: Two cents of advice by the time-tested (read: seasoned ) authors: there is a lot of marketing also in science, and you will need part of it to advance in your career, but avoid following the hype of the moment if you hear a voice in your head telling you that there is something weird and that there must be a better way to solve the same problem.

Avoid the hell of equality: science, business, and society thrive on diversity, and there is no chance of being different if you do what everybody does. And, when solving complex problems, do not imitate viruses or metals, imitate human learning and self-improving abilities!