Gerard Cornuejols

Two papers and their four authors were awarded the 1977 Lanchester Prize at the ORSA/TIMS Joint Meeting in Los Angeles. The winning papers were:

• Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms," by Gerard Cornuejols, Marshall L. Fisher and George L. Nemhauser, Management Science, April 1977.
• "A Probabilistic Analysis of Partitioning Algorithms for the Travelling-Salesman Problem in the Plane," by Richard M. Karp, Mathematics of Operations Research, August 1977.

The award was presented by Peter J. Kolesar of Columbia University, Chairman of the 1977 Lanchester Prize Committee. Dr. Kolesar made the following comments:

• The solution of many important practical operations research problems depends in part on our ability to solve efficiently a wide variety of combinatorial optimization problems of formidable size. Operations Researchers, practitioners and theoreticians alike have struggled with these problems for nearly thirty years. Only relatively recently have theoretical results of Steven Cook and Richard Karp confirmed what some operations researchers had long suspected -- that many of these problems are intrinsically hard, that they are intimately related to each other, and that it is unlikely we will ever have algorithms guaranteed to find optimal solutions to large problems without excessive computational labor.
• Thereupon, researchers have given increasing attention to the study of heuristic algorithms of the type practitioners have long been compelled to use. Much of this work focuses on answering the question of how badly a heuristic might perform — the study of worst case bounds. The work of Ronald Graham, Michael Garey, and David Johnson at Bell Laboratories broke the ground for this pursuit. The conservatism of worst case bounds does not always provide adequate guidance to the practitioner. Indeed, actual experience with heuristics is often quite good, and this has led to the study of a related set of questions about the performance of heuristic algorithms on average, and about their relative frequency of bad performance. Actually, it appears that both worst case and average case analysis will be useful in improving the design and performance of heuristics.
• In recognition of the quality of their contributions to the science and art of heuristic problem solving, and in the expectation that this line of inquiry will continue to contribute to real understanding and better ability to solve important practical problems, we award the 1977 Lanchester Prize to two papers. The first paper analyzes a particular banking application of the plant location problem from a worst case point of view. It obtains the sharpest possible bounds for some heuristics and then compares them computationally. The second paper is the first major application of probabilistic analysis to a combinatorial optimization problem. It develops the ideas necessary for this analysis and applies them to a powerful partitioning technique for solving the traveling salesman problem.