Request Username
Can't sign in? Forgot your username?
Enter your email address below and we will send you your username
IJOC Test of Time Papers
In 2020, the INFORMS Journal on Computing implemented the Test of Time Paper Award to recognize the impactful heritage of the journal:
- Number of awards: One per calendar year.
- Goal: Recognition of a published IJOC paper that has proven impactful over a length of time. Considerations can be citations per year, downloads per year, influence of sparking new areas of research, practical implications, significance of findings, and so forth.
- Criteria: All those papers published in the time window are considered. A paper can be recognized with this award only once. The time window is defined as a rolling window of 5 years starting 15 years ago.
- Deadline: None. Papers are considered on an annual basis.
- Selection: Small committee appointed by the editor-in-chief.
- Recognition: Certificate of Test of Time Award (transmitted by email) and annual recognition in the journal (paper, authors, affiliations, citation).
- Procedure: The set of papers published in IJOC during the time window with their citations per year (since publishing) will be sent to the committee members for their deliberation. A winner is selected by the committee, and the editor-in-chief is notified.
Test of Time Award for Papers Published in IJOC, 2007-2011
Peter Frazier, Warren Powell, Savas Dayanik
The Knowledge-Gradient Policy for Correlated Normal Beliefs
INFORMS Journal on Computing, Volume 21, Issue 4, Fall 2009
https://doi.org/10.1287/ijoc.1080.0314
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 38, Issue 1, January-February 2026:
This paper introduces the now well-known knowledge-gradient (KG) method for gathering information when faced with a black-box objective, where query measurements may be both costly and noisy. The focus of the paper is on ranking and selection, but the KG method can be used also to study multiarmed bandit problems and many other models in Bayesian information collection. This very broad applicability led to a lively KG research area that continues to this day, with new developments studied in modern machine learning. It is an excellent example of work that has stood the test of time.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Karla Hoffman, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2006-2010
Edward Rothberg
An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions
INFORMS Journal on Computing, Volume 19, Issue 4, Fall 2007
https://doi.org/10.1287/ijoc.1060.0189
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 37, Issue 6, November-December 2025:
This paper provides an elegant and computationally efficient method for applying evolutionary algorithms to general mixed integer linear optimization problems (MIPs). It integrates the ideas of reproduction, crossover, and mutation into general MIP methodology. The novelty is that it chooses parents by collecting feasible solutions found during the solution process, ranks the parents based on solution quality, and then applies the evolutionary properties of mating and mutation to determine the next generation of solutions. The technique requires no information about the underlying structure of the problem and is, therefore, applicable to any MIP problem. The impact that this paper has had on MIP solution technology through its implementation in both commercial and open-source solvers is enormous. The paper continues to be highly cited.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Karla Hoffman, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2005-2009
Rommel G. Regis, Christine A. Shoemaker
A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions
INFORMS Journal on Computing, Volume 19, Issue 4, Fall 2007
https://doi.org/10.1287/ijoc.1060.0182
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 37, Issue 4, July-August 2025:
The authors propose and test methods for solving global optimization problems in which the function to be minimized is expensive to compute. It can be thought of as a black-box function or a simulation experiment. A single objective function evaluation can take hours, and derivatives may not be available. The authors propose two stochastic radial basis function (RBF) methods in which the expensive objective function evaluations are approximated by a surrogate model. The surrogate model allows for a stochastic and much more extensive exploration of the solution space. These new methods are tested against six alternative global optimization methods on 17 multimodal test problems and a real-world groundwater bioremediation application involving partial differential equations. Their multistart local metric stochastic RBF (MSRBF) algorithm is the overall winner. This highly cited article is noteworthy for several reasons. First, the authors tackle a difficult and general optimization problem. Second, they develop new algorithms and prove a convergence result. Third, they carry out comprehensive computational experiments. Finally, the success of the new algorithms demonstrates that they can be applied to other real-world optimization problems.
Please note the link included in their retrospective of the newly established IJOC GitHub repository with the code associated with this landmark paper.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Karla Hoffman, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2004-2008
Zsolt Ugray, Leon Lasdon, John Plummer, Fred Glover, James Kelly, Rafael Martí
Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization
INFORMS Journal on Computing, Volume 19, Issue 3, Summer 2007
https://doi.org/10.1287/ijoc.1060.0175
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 32, Issue 1, Winter 2020:
Not only has this paper attracted a large number of citations, but it continues to be highly cited to this day, many years following publication. In fact, a significant number of the publications are recent, showing that the authors were ahead of their time.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2003-2007
Juan Feng, Hemant K. Bhargava, David M. Pennock
Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms
INFORMS Journal on Computing, Volume 19, Issue 1, Winter 2007
https://doi.org/10.1287/ijoc.1050.0135
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 32, Issue 2, Spring 2020:
This highly cited paper continues to be an important reference for the community of researchers studying this rapidly growing sector of the advertising market. The work is a very nice example of the reach of operations research techniques into the new economy.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2002-2006
Joseph Abate, Ward Whitt
A Unified Framework for Numerically Inverting Laplace Transforms
INFORMS Journal on Computing, Volume 18, Issue 4, Fall 2006
https://doi.org/10.1287/ijoc.1050.0137
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 32, Issue 4, Fall 2020:
The paper shows that different components can be combined to create algorithms that are more effective than individual methods. It continues to be cited by researchers who use it as a springboard for new methods.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2001-2005
David Applegate, William Cook, and André Rohe
Chained Lin-Kernighan for Large Traveling Salesman Problems
INFORMS Journal on Computing, Volume 15, Issue 1, Winter 2003
https://doi.org/10.1287/ijoc.15.1.82.15157
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 33, Issue 2, Spring 2021:
This work is part of a series of papers that have been instrumental in demonstrating the effectiveness of advanced heuristics and mathematical optimization to produce optimal, or near-optimal, solutions to very large TSPs with as many as 25,000,000 cities. The implementation is also part of the pioneering Concord software. It is hard to overestimate the impact of this research on the optimization community.
Selection Committee: John Chinneck (chair), Bill Cook (who naturally was recused from the deliberations of this particular award), Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 2000-2004
Myra Spiliopoulou, Bamshad Mobasher, Bettina Berendt, Miki Nakagawa
A Framework for the Evaluation of Session Reconstruction Heuristics in Web-Usage Analysis
INFORMS Journal on Computing, Volume 15, Issue 2, Spring 2003
https://doi.org/10.1287/ijoc.15.2.171.14445
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 33, Issue 3, Summer 2021:
The paper made an important contribution to research on web-usage analysis at the time of its publication and continues to be cited as data mining has expanded to user logs in social media in addition to web use.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1999-2003
Paolo Toth and Daniele Vigo
The Granular Tabu Search and Its Application to the Vehicle-Routing Problem
INFORMS Journal on Computing, Volume 15, Issue 4, Fall 2003
https://doi.org/10.1287/ijoc.15.4.333.24890
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 33, Issue 4, Fall 2021:
Toth and Vigo proposed a granular tabu search approach that enabled users to obtain excellent vehicle-routing solutions within reasonably short computing times. The concept was easy to adapt to other important optimization problems. ...This paper has been cited more than 600 times according to Google Scholar.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1998-2002
Zonghao Gu, George L. Nemhauser, and Martin W. P. Savelsbergh
Lifted Cover Inequalities for 0-1 Integer Programs: Computation
INFORMS Journal on Computing, Volume 10, Number 4, Fall 1998
/doi/abs/10.1287/ijoc.10.4.427
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 36, Issue 2, Mar-Apr 2024:
One of the great success stories in operations research has been the remarkable string of improvements in the practical performance of mixed integer-programming solvers over wide classes of applied models. An important component of that success was the early demonstration of the power of combinatorially-defined cutting planes by Gu, Nemhauser, and Savelsbergh. Their computational study focuses on the use of lifted cover inequalities for models with 0-1 valued variables. The paper emphasizes the importance of careful algorithmic and implementation choices, concluding with a list of practical recommendations that can be immediately adopted in solvers for large-scale problem instances. Their work is cited in papers covering a remarkable range of problem classes and it remains a shining example for the study and reporting of computational issues in IP methodology.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1997–2001
Vipul Jain and Ignacio E. Grossmann
Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems
INFORMS Journal on Computing, Volume 13, Number 4, Fall 2001
/doi/abs/10.1287/ijoc.13.4.258.9733
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 36, Issue 3, May-Jun 2024:
This paper is an early and compelling application of logical Benders decomposition, where the master problem is solved by a mixed-integer program and the subproblems by constraint programming. The authors consider a scheduling problem on a pool of heterogenous machines, where the master problem allocates the jobs to the machines, the subproblems schedule the machines, and a logical Benders decomposition connects them. In addition to its contributions to the considered application, the paper was instrumental in stimulating significant and substantial research in logical Benders decomposition, branch and check, and branch and price and check, with applications in many domains including routing and scheduling.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1996-2000
Vittorio Maniezzo
Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
INFORMS Journal on Computing, Volume 11, Issue 4, Fall 1999
https://doi.org/10.1287/ijoc.11.4.358
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 37, Issue 2, March-April 2025:
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.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1995-1999
Anuj Mehrotra and Michael Trick
A Column Generation Approach for Graph Coloring
INFORMS Journal on Computing, Volume 8, Issue 4, Fall 1996
/doi/10.1287/ijoc.8.4.344
For the Test of Time Award Citation and a reflection on the paper and this award by the author, see Note from the Editor, Volume 36, Issue 6, Nov-Dec 2024:
The paper describes developments in the well-known CONOPT nonlinear programming solver. It is notable for a comparison of the algorithmic differences between sequential linearization algorithms and generalized reduced gradient algorithms. By describing the careful selection and implementation of the algorithmic parts of CONOPT (e.g., selection and factorization of the basis, search direction selection, and line search procedures), the paper underscores the impact that the particulars of these decisions have on solver efficiency and robustness. This is an excellent example of good work at the interface of operations research and computer science. CONOPT has been applied to problems in many fields, and the paper continues to be frequently cited to this day.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1994–1998
J. Abate and W. Whitt
Numerical Inversion of Laplace Transforms of Probability Distributions
INFORMS Journal on Computing, Volume 7, Issue 3, Winter 1995
/doi/abs/10.1287/ijoc.7.1.36
For the Test of Time Award Citation and a reflection on the paper and this award by the author, see Note from the Editor, Volume 36, Issue 4, Jul-Aug 2024:
This work describes an elegant, computationally efficient, and accurate method of numerical inversion of Laplace transforms, with an eye toward transforms of cumulative distribution functions. Inverting the transforms is important in the analysis of stochastic systems such as queuing networks. Transformed functions are often much easier to work with computationally, but then, of course, an inversion is needed to access the results. This paper operationalizes previous work in the form of an algorithm and a software implementation that was made available by the authors, which contributed to ongoing research. Although the method is relatively simple, rigorous confirmation of the accuracy required significant effort and is part of the contribution of this work.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1993-1997
Arne Stolbjerg Drud
CONOPT: A Large-Scale GRG Code
ORSA Journal on Computing, Volume 6, Issue 2, Spring 1994
/doi/abs/10.1287/ijoc.6.2.207
For the Test of Time Award Citation and a reflection on the paper and this award by the author, see Note from the Editor, Volume 36, Issue 1, Jan-Feb 2024:
The paper is beautifully written, developing and explaining difficult concepts in branch-cut-and-price methodology in an easy-to-grasp setting. Their elegant work has long served as an important template in the application of linear programming techniques to the solution of difficult optimization models. It will continue to do so for years to come.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1992-1996
Roberto Battiti and Giampiero Tecchiolli
The Reactive Tabu Search
ORSA Journal on Computing, Volume 6, Issue 2, Spring 1994
/doi/epdf/10.1287/ijoc.6.2.126
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 35, Issue 6, Nov-Dec 2023:
This paper describes the new Reactive Tabu Search 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.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1991-1995
James C. Bean
Genetic Algorithms and Random Keys for Sequencing and Optimization
ORSA Journal on Computing, Volume 6, Issue 2, Spring 1994
/doi/10.1287/ijoc.6.2.154
For the Test of Time Award Citation and a reflection on the paper and this award by the author, see Note from the Editor, Volume 35, Issue 4, Jul-Aug 2023:
Genetic algorithms (GAs) have been around since the 1960s. They have been used by computer scientists and operations researchers to find good solutions to optimization problems. In a GA, feasible solutions mimic a population of individuals which mate and produce offspring that survive based on Darwin’s notion of survival of the fittest. The idea is that individuals (i.e., feasible solutions) tend to become more fit (i.e., less costly) from one generation to the next. The fundamental operations in a GA are reproduction and crossover. These must be defined in a GA and applied at each generation.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1990-1994
David Applegate and William Cook
A Computational Study of the Job-Shop Scheduling Problem
ORSA Journal on Computing, Volume 3, Issue 2, Spring 1991
/doi/abs/10.1287/ijoc.3.2.149
For the Test of Time Award Citation and a reflection on the paper and this award by the authors, see Note from the Editor, Volume 35, Issue 3, May-Jun 2023:
This paper, together with one by Carlier and Pinson that closed the famous MT-10 problem, started a golden decade for research in job-shop scheduling and scheduling in general. It demonstrated that challenging job-shop problems could now be solved optimally in a few minutes, using beautiful mathematical programming concepts, including cutting planes and combinatorial relaxations. It was widely influential, studied both complete and heuristic methods, closed a number of open problems, and promoted the edge-finder algorithm that became standard in commercial scheduling packages.
Selection Committee: John Chinneck (chair), Bill Cook (recused for this selection), Bruce Golden, Pascal Van Hentenryck, and David Woodruff.
Test of Time Award for Papers Published in IJOC, 1989-1993
Fred Glover
Tabu Search—Part I
ORSA Journal on Computing, Volume 1, Issue 3, Summer 1989
https://doi.org/10.1287/ijoc.1.3.190
Fred Glover
Tabu Search—Part II
ORSA Journal on Computing, Volume 2, Issue 1, Winter 1990
https://doi.org/10.1287/ijoc.2.1.4
For the Test of Time Award Citation and a reflection on the paper and this award by the author, see Note from the Editor, Volume 34, Issue 3, May-June 2022:
This awardee is unique for several reasons. First, it encompasses two papers, and these papers are the most cited (and arguably the most influential) in IJOC history. Second, the author, Fred Glover, is a titan of our field, and this year (2022), he celebrates his 80th birthday.
For more, see Fred Glover's Unforeseen Consequences of “Tabu” Choices—A Retrospective, Volume 34, Issue 3, May-June 2022.
Selection Committee: John Chinneck (chair), Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff.