Past Awards
The 2012 John von Neumann Theory Prize of INFORMS is awarded to George Nemhauser and Laurence Wolsey for their outstanding and lasting contributions to integer optimization and example setting scholarship. Both individually and jointly, they have advanced significantly our understanding of discrete optimization both from theoretical and practical perspectives.
George Nemhauser is one of the most influential scholars in the operations research and optimization community. In his over 50 years career (his Phd was in 1961), George has advanced the theory and practice of discrete optimization through numerous articles, influential books and computer codes. He is the only researcher who has won the Lanchester prize twice. In 1978, he (together with G. Cornuejols and M. Fisher) won the Lanchester prize for his pioneering analysis of an approximation algorithm for a facility location problem. In 1989, George and Laurence won the Lanchester prize for their book "Integer Programming and Combinatorial Optimization’’. He is a member of their National Academy of Engineering and has received the Kimball medal.
Laurence Wolsey has a similarly long career and has become one of the most recognized members of our community due to his sustained and constant high-level contributions to many aspects of optimization. Earlier this summer Laurence was the recipient of the Dantzig prize for contributing significantly to foundational understanding of the geometry of mixed-integer optimization, to duality theory in discrete optimization, and to the development of effective new methods to the variety of applications, particularly in production planning and scheduling.
George and Laurence pioneered the study of polyhedral combinatorics when it was not yet fashionable and practically successful to use cutting planes and the like in integer programming. They both contributed to facility location, cutting stock and stochastic programming, and in particular to various aspects of production and production planning.
George and Laurence have jointly published more than 10 papers that range from a recursive procedure to generate all cuts for 0-1-mixed-integer program, via uncapacitated facility location, to maximization of submodular set functions and worst-case and probabilistic analysis of algorithms as well as travelling salesman problems. Their joint book "Integer and Combinatorial Optimization" has had a significant influence on the community. Their development of mixed-integer rounding (MIR) are the prime tools nowadays in general codes for the solution of integer and mixed-integer programming problems.
They also contributed significantly to the development of codes for the solution of general or specific integer programming problems. The MINTO development that George did (together with Savelsbergh and Sigismondi) was a precursor of modern branch-and-cut codes. The book "Production Planning by Mixed-integer Programming" by Laurence and Yves Pochet is a pioneering extensive monograph showing how to model and solve relevant planning problems.
Both George and Laurence have been outstanding research supervisors and have influenced the research directions of many other younger colleagues by their advice and guidance. They both share their insights and graciously provide ideas to many other colleagues.
The first recipient of the INFORMS Optimization Society Khachiyan Prize, to be awarded to an individual or a team for life-time achievements in the area of optimization, is George Nemhauser, the A. Russell Chandler Chaired Professor in Industrial and Systems Engineering at the Georgia Institute of Technology, Atlanta, Georgia.
During a remarkable academic career of so far about 50 years George Nemhauser has grown into one of the world's foremost experts in discrete optimization and has become one of the most recognized members of the INFORMS community. The basis for his outstanding position as an OR scientist are his fundamental contributions to the theory and practice of integer programming and combinatorial optimization. His integer programming books have guided the field for more than thirty years, each introducing a host of new techniques for handling IP models in theory and practice. George's nearly two hundred research papers in the field are unmatched in their breadth of coverage.
George has shown a unique ability to find, solve, and present applied work in Operations Research; but first and foremost he is a superb contributor to the theory underlying optimization techniques. This is evident from his publications throughout his whole career, starting with traveling-salesman-problem work in 1962 and continuing through his recent papers on piecewise-linear optimization. Fundamental models and techniques covered by George include Lagrangian optimization, dynamic programming, capital budgeting, set partitioning, cutting planes, branch-and-price, transportation problems, graph coloring, vertex packing, submodular functions, facility location, cutting stock, stochastic programming, and so on. State-of-the-art software relies heavily on the use of cutting planes, and George Nemhauser was an early proponent of this approach. MINTO, a code he developed in collaboration with Savelsbergh and Sigismondi, was a precursor of modern branch-and-cut codes.
George Nemhauser has served ORSA as council member, president, and editor of Operations Research, and he is past chair of the Mathematical Programming Society. He is the founding editor of Operations Research Letters, and co-editor of Handbooks of Operations Research and Management Science.
George has served various governmental agencies, including the NSF, the National Institute of Standards and Technology (NIST), and the National Research Council (NRC). His honors and awards include the Kimball Medal, the Lanchester Prize (twice awarded), Morse lecturer of ORSA, and membership in the National Academy of Engineering.
Selection Committee
Martin Grötschel, Arkadi Nemirovski, Panos Pardalos, Tamás Terlaky (chair).
George Nemhauser's acceptance video.
The Lanchester Prize Committee chose three "deserving" individuals and two "excellent" publications for the 1989 prize.
The 1989 Lanchester Prize was shared by Jean Walrand, author of An Introduction to Queueing Networks (Prentice Hall, 1988), and George L. Nemhauser and Laurence A. Wolsey, whose combined efforts produced Integer and Combinatorial Optimization (John Wiley, 1988). Nemhauser becomes the first two-time winner of the prestigious award. He won it in 1977 for the paper, "Location of Bank Accounts to Optimize Float: An Analytic Study of an Exact and Approximate Algorithm," coauthored by G. Cornuejols and M.L. Fisher.
"George and I are both delighted and surprised by this award, " said Wolsey, speaking on behalf of himself and Nemhauser. "It cannot be often that an introduction to an introduction gets a prize. Two years ago the Lanchester Prize was, you remember, given to Lex Schrijver for his remarkable book, Linear and Integer Programming, which was just the introductory chapters of a book on combinatorial optimization he had been writing for years. One could regard our book as an introduction to his book."
Wolsey thanked a long list of individuals and institutions "who inspired and helped us along the way," incl`uding Martin Beale, Jack Edmonds, Ray Fulkerson, Ralph Gomory, Jack Mitten, Jerry Shapiro, John Little, Cornell, M.l.T., Georgia Tech and the University of Louvain in Brussels, Belgium.
In their book Integer and Combinatorial Optimization, Nemhauser and Wolsey set out to write a graduate text and reference hook for researchers and practitioners that unifies theory and algorithms. The committee found the authors far exceeding their goal, adding that "many believe they have defined the way people will think about and discuss the field of integer programming and combinatorial optimization for years to come."
"George Nemhauser and Laurence Wolsey capture the progress that has been made in discrete optimization over the past two decades. They include many results that heretofore have only appeared in research journals and monographs, and have done so in a lucid and accessible style. Their coverage is broad, capturing essentially all of this rapidly changing field but also condenses, simplifies and synthesizes this remarkable amount of information. "
The citation sums up the importance of Nemhauser and Wolsey's work with the following words: "Whether readers are planning to conduct research, use practical algorithms, or are fascinated by theory in discrete optimization, this book is a must for their libraries."
Nemhauser, of the School of Industrial and Systems Engineering at Georgia Institute of Technology in Atlanta, and Wolsey, of the Center for Operations Research and Economics at the Catholic University of Louvain, Belgium, received honorable mention in the Lanchester Prize competition last year.
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.