John von Neumann Theory Prize

2015 Winner(s): Vašek Chvátal, Concordia University, Dept. of Computer Science & Software Engineering ; Jean Bernard Lasserre, CNRS, France
Citation:

This award recognizes their seminal and profound contributions to the theoretical foundations of optimization. Through their work in the domains of integer programming and polynomial optimization, respectively, Chvátal and Lasserre developed the mathematical theory and corresponding computational approaches to tackle hard computational problems that compute strengthened bounds via tractable convex relaxations. The notions of Chvátal rank and the Lasserre hierarchy each have impact well beyond their initial research spheres and are simultaneously elegant mathematics and the foundations for new algorithmic approaches.

Vašek Chvátal's body of theoretical research work has brought elegance to the field of operations research, and in particular linear and integer programming, algorithms, complexity, graph theory, and computation, that is unmatched. It is easy to select Chvátal's 1973 cutting-plane paper ``Edmonds polytopes and a hierarchy of combinatorial problems'' as one of the top papers in the history of integer programming, in which Chvátal shed new light on Gomory’s fractional cutting planes for solving integer programs and, even more importantly, introduced the concept of the rank of valid inequalities and polyhedra. This new idea of rank provided the structure to understand the difficult task of creating integral polyhedral from relaxations and impacted the subsequent development of theory and algorithms. His slogan combinatorics = number theory + linear programming became the rallying cry for researchers in the following decades, when cutting planes went on to be the most important component of the expansion and increased depth of the field. In the area of algorithms, Chvátal's 1979 paper ``A greedy heuristic for the set-covering problem'' introduced an amazing dual argument, showing a logarithmic optimality ratio for a simple greedy algorithm. The LP-duality line-of-thought is now a central tool in the area of approximation methods for NP-hard problems. In complexity theory, Chvátal introduced the notion of cutting-plane proofs that has become an important model of computation. In 1988, he also co-authored, with Szemerédi, the influential paper ``Many hard examples for resolution,'' describing the use of randomization to create a class of satisfiability problems that is difficult for the resolution proof system. Chvátal and Szemerédi do not construct specific examples of their class, but rather show that with high probability a random example is difficult. This is an elegant blueprint for a possible attack on P versus NP itself. In the early 1990s, Chvátal turned his research focus to computational work, tackling the traveling salesman problem with the concrete aim of solving large instances to exact optimality. In 1973, he introduced the concept of comb inequalities that had taken the cutting-plane approach to the TSP to new heights in the 1970s and 1980s. In this new work, Chvátal succeeded in bringing to bear on the TSP many of the further ideas he had developed in his general studies of integer programming, algorithms, and complexity. This research, together with Applegate, Bixby, and Cook, is described in the 2007 Lanchester Prize winning book The Traveling Salesman: A Computational Study. Their Concorde code gradually worked through the entire TSPLIB challenge set, including the exact solution of an instance consisting of 85,900 cities from a VLSI application. This success is a primary example of the power of sophisticated mathematical tools to solve seemingly intractable optimization models.

Jean Lasserre’s fundamental work on optimization has provided the mathematical framework to solve an important class of optimization problems--polynomial optimization--in which one aims to minimize a polynomial function subject to polynomial inequality constraints, which has been applied in areas ranging from control theory to machine learning-inspired clustering problems, and computer vision to quantum cryptography. Lasserre’s paper, “Global optimization with polynomials and the problem of moments,” created the field of polynomial optimization, and outlined the major tools and underlying mathematics of virtually all work in the area that followed. These problems are non-convex, very hard to solve, and previous work settled for finding only a local optimum. Lasserre introduced an ingenious new method based on reformulating the problem as a convex optimization problem over the set of measures having a prescribed support; next he devised a scheme of hierarchical approximations for the original problem based on exploiting necessary conditions for sequences of moments of measures. He not only proved the convergence of the bounds to the optimum value of the original hard problem, but also used this as the basis for an effective computational method for computing global optimizers, relying on the fact that these hierarchical bounds can be computed via semidefinite programming. This is a landmark achievement in the development of the mathematics of optimization. A key aspect of this paper was the use of techniques from real algebraic geometry to derive certificates of positivity using representations by sums of squared polynomials. Building on this in his subsequent paper, “A sum of squares approximation of nonnegative polynomials,” Lasserre gave an elegant new proof of the central element in this theory: any nonnegative polynomial can be approximated by sums of squares. Combining convex duality theory and a moment-theoretic result, he constructed approximating polynomials that are both simple and explicit. One consequence is a vast simplification of his original relaxation hierarchy; this simplification has enabled it to be integrated in a plethora of new directions, where one important exemplar is in the theory of approximations for NP-hard discrete optimization problems, where the “Lasserre hierarchy” is at the heart of current work to both prove and disprove the unique games conjecture. This work was also Lasserre’s starting point for further generalizations, such as his work on the generalized moment problem, which significantly extends the reach of these methods.

Purpose of the Award

The John von Neumann Theory Prize is awarded annually to a scholar (or scholars in the case of joint work) who has made fundamental, sustained contributions to theory in operations research and the management sciences. The award is given each year at the INFORMS Annual Meeting if there is a suitable recipient. Although the Prize is normally given to a single individual, in the case of accumulated joint work, the recipients can be multiple individuals.

 

The Prize is awarded for a body of work, typically published over a period of several years. Although recent work should not be excluded, the Prize typically reflects contributions that have stood the test of time. The criteria for the Prize are broad, and include significance, innovation, depth, and scientific excellence.

 

The award is $5,000, a medallion and a citation.

Past Awardees

2015 Winner(s)
Vašek Chvátal, Concordia University, Dept. of Computer Science & Software Engineering Jean Bernard Lasserre, CNRS, France
2014 Winner(s)
Nimrod Megiddo, IBM
2013 Winner(s)
Michel L Balinski, C.N.R.S. and Ecole Polytechnique
2012 Winner(s)
Laurence A. Wolsey, Université Catholique de Louvain George L. Nemhauser, Georgia Institute of Technology, Dept. of Industrial & Systems Engineering
2011 Winner(s)
Gerard P. Cornuejols, Carnegie Mellon University, Tepper School of Business
2010 Winner(s)
Peter Glynn, Stanford University Søren Asmussen, Aarhus University, Denmark
2009 Winner(s)
Yurii Nesterov, CORE/UCL Yinyu Ye, Stanford University, Department of Management Science & Engineering
2008 Winner(s)
Frank P. Kelly, Centre for Mathematical Science, University of Cambridge
2007 Winner(s)
Arthur F. Veinott, Jr., Stanford University
2006 Winner(s)
Martin Grötschel, ZIB
Konrad-Zuse-Zentrum
László Lovász, Eotvos University, Institute of Mathematics Alexander Schrijver, CWI, National Research Institute for Mathematics & Computer Science
2005 Winner(s)
Robert J. Aumann, The Hebrew University of Jerusalem, Center for Rationality
2004 Winner(s)
J. Michael Harrison, Stanford University, Graduate School of Business
2003 Winner(s)
Arkadi Nemirovski, Georgia Institute of Technology, School of ISyE Michael J. Todd, Cornell University
School of Operations Research and Information
2002 Winner(s)
Cyrus Derman, Professor Operations Research, Columbia University Donald L. Iglehart, Stanford University
2001 Winner(s)
Ward Whitt, Columbia University, Industrial Engineering & Operations Research Dept.
2000 Winner(s)
Ellis L. Johnson, School of Industrial & Systems Engineering, Georgia Institute of Technology Manfred W. Padberg, New York University, Stern School of Business
1999 Winner(s)
R. Tyrrell Rockafellar, University of Washington, Dept. of Mathematics
1998 Winner(s)
Fred W. Glover, OptTek Systems, Inc.
1997 Winner(s)
Peter Whittle
1996 Winner(s)
Peter C. Fishburn
1995 Winner(s)
Egon Balas, Carnegie Mellon University, Tepper School of Business
1994 Winner(s)
Lajos Takacs
1993 Winner(s)
Robert Herman, University of Texas-Austin
1992 Winner(s)
Alan J. Hoffman, IBM Philip S. Wolfe, IBM
1991 Winner(s)
Richard E. Barlow, University of California-Berkeley Frank Proschan
1990 Winner(s)
Richard M. Karp, University of California - Berkeley, Dept. of Electrical Engineering & Computer Science
1989 Winner(s)
Harry M. Markowitz , Baruch College
1988 Winner(s)
Herbert A. Simon
1987 Winner(s)
Samuel Karlin , Stanford University
Dept of Mathematics
1986 Winner(s)
Kenneth J. Arrow , Stanford University, Dept. of Economics
1985 Winner(s)
Jack Edmonds, University of Waterloo, Dept. of Combinatorics & Optimization
1984 Winner(s)
Ralph E. Gomory , Alfred P. Sloan Foundation
1983 Winner(s)
Herbert E. Scarf, Yale University
1982 Winner(s)
Abraham Charnes William W. Cooper, University of Texas - Austin, MSIS Department Richard J. Duffin
1981 Winner(s)
Lloyd S. Shapley , University of California - Los Angeles, Dept. of Economics
1980 Winner(s)
David Gale Harold W. Kuhn, Princeton University Albert W. Tucker
1979 Winner(s)
David Blackwell , University of California - Berkeley
1978 Winner(s)
John F. Nash, Princeton University, Mathematics Dept. Carlton E. Lemke
1977 Winner(s)
Felix Pollaczek
1976 Winner(s)
Richard Bellman
1975 Winner(s)
George B. Dantzig, Stanford University
Featured Award

Nominations due July 31, 2016

The Prize Committee is currently seeking nominations, which should be in the form of a letter (preferably email) addressed to the prize committee chair (below), highlighting the nominee's accomplishments. Although the letter need not contain a detailed account of the nominee's research, it should document the overall nature of his or her contributions and their impact on the profession, with particular emphasis on the prize's criteria. The nominee's curriculum vitae, while not mandatory, would be helpful.

Click here for instructions »

About the Award/Namesake

John von Neumann

John von Neumann was a brilliant mathematician, synthesizer, and promoter of the stored program concept, whose logical design of the IAS became the prototype of most of its successors - the von Neumann Architecture. von Neumann was invited to visit Princeton University in 1930, and when the Institute for Advanced Studies was founded there in 1933, he was appointed to be one of the original six Professors of Mathematics, a position which he retained for the remainder of his life. Postwar von Neumann concentrated on the development of the Institute for Advanced Studies (IAS) computer and its copies around the world. His work with the Los Alamos group continued and he continued to develop the synergism between computers capabilities and the needs for computational solutions to nuclear problems related to the hydrogen bomb.

Learn more about John von Neumann »

Committee

2016 Committee Chair:

David B. Shmoys
Professor
Cornell University
Ithaca, NY 14853-3801 U.S.A.

email: david.shmoys@cornell.edu

Click here for committee information