Note from the Editor

We continue to announce the winners of the INFORMS Journal on Computing 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 1996–2000. What follows is the citation from the award committee and then, a reflective interview with the author concerning the paper.

I want to thank the committee for their superb efforts, and I 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 1996–2000 is awarded to

Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem

Vittorio Maniezzo

INFORMS Journal on Computing 11(4):358–369, 1999

https://pubsonline.informs.org/doi/10.1287/ijoc.11.4.358

Test of Time Award Citation 1996–2000

This work describes new algorithms for solving the difficult combinatorial quadratic assignment problem using advances in ant system heuristics that result in the approximate nondeterministic tree-search system. The main advances include the use of lower bounds for minimization problems, improvements in computational efficiency, and techniques to avoid stagnation in the solutions. Some of the algorithmic ideas are extended to control the branching in an exact tree-search algorithm for the quadratic assignment problem, which is the first hybridization of ant colony algorithms and branch-and-bound tree search strategies. These ideas influenced later developments in ant colony algorithms and continue to be frequently cited.

Retrospection from the Author Vittorio Maniezzo

First of all, many thanks to the editor-in-chief Alice E. Smith and the selection committee for selecting my paper for the INFORMS Journal of Computing Test of Time Paper Award for 1996–2000.

I was notified of my selection in the month of January, and I find it a most appropriate month given the content of the paper. In fact, this is the month dedicated to the ancient Roman god Janus, the god, among many other things, of beginnings and transitions. He is usually depicted with a two-faced head, one looking backward and one looking forward. Such is the content of the paper.

The paper proposes a variant of an ant colony metaheuristic applied to the quadratic assignment problem. The problem needs no introduction; it is a classic of combinatorial optimization and was chosen for that very reason.

The variant is more individual. The work was conceived just after the golden age of metaheuristics when the main paradigms were presented: simulated annealing (earlier, Kirkpatrick et al. 1983), genetic algorithms (Holland 1975 but mainly, Goldberg 1989), tabu search (Glover 1989), greedy randomized adaptive search procedure (Feo and Resende 1995), variable neighborhood search (Mladenovic and Hansen 1997), particle swarm optimization (Kennedy and Eberhart 1995), and of course, ant colony optimization (Dorigo et al. 1996).

The field was going to evolve, but something new had to be injected to get around the exhausted trend of natural process metaphors. What I thought might be relevant was mathematical programming (MP). Sure, MP-based heuristics already existed, think of Lagrangian heuristics, but they were uncommon in metaheuristics and generally seen as a by-product of an exact approach.

MP comes into play in the paper by using a linear assignment problem as a means of evaluating partial solution expansions. Ant colony is in fact a constructive heuristic where partial solutions are iteratively expanded until complete solutions are obtained. Expansions are usually evaluated by an ad hoc formula, but a linear assignment bound computed on the remaining elements, or its duals computed at some point during the search, could also be used.

This simple use of MP within a metaheuristic turned out to be the forward-looking face.

Unbeknownst to me, my feeling about the opportunity of introducing MP into heuristic design was shared by several other researchers, and this eventually gave rise to the field of matheuristics (Maniezzo et al. 2021) (i.e., heuristics designed around a mathematical model), which was baptized in the year 2006 (Maniezzo 2006).

Back to the algorithm, expanding a partial solution by evaluating expansions against a bound is of course the basic operation of standard tree search. Ant colony incorporates this into its randomized, nondeterministic construction process, so the result is not an exact solution but an approximate one. Hence the acronym.

The original code and test instances reported in the paper are now available in a Git repository (Maniezzo 1999).

In conclusion, I would like to say that this award makes it possible to appreciate the impact of this research, and I am very grateful for this recognition.