Past Awards
In recognition of his fundamental contributions to integer programming and combinatorial optimization, the 2000 John von Neumann Theory Prize was awarded jointly to Ellis L. Johnson and Manfred W. Padberg. Their work combines theory with algorithm development, computational testing, and solution of hard real-world problems in the best tradition of Operations Research and the Management Sciences. In their joint work with Crowder and in subsequent work with others, they showed how to formulate and solve efficiently very large-scale practical 0-1 programs with important applications in industry and transportation.
Ellis Johnson earned his PhD from the University of California at Berkeley in 1965 and, after several years at Yale University, joined the IBM T. J. Watson Research Center in Yorktown Heights. In the early seventies he produced three important and influential papers—two of them with Ralph Gomory—which developed and extended in significant ways the group theoretic approach to integer programming pioneered by Gomory. In particular, Johnson showed how the approach can be extended to the case of mixed integer programs. As an outgrowth of this work, Johnson contributed decisively to the development of what became known as the subadditive approach to integer programming.
Still in the seventies, in a seminal paper co-authored with Jack Edmonds, Johnson showed how several basic optimization problems defined on graphs can be solved in polynomial time by reducing them to weighted matching problems. One example is finding minimum T-joins, i.e., edge sets whose only endpoints of odd degree are those in a specified vertex set T. An important special case is the seemingly difficult problem of finding a shortest tour in a graph that traverses every edge at least once, known as the Postman problem. The stark contrast between the polynomial solvability of this problem and the intractability of the traveling salesman problem in which the tour is supposed to traverse vertices rather than edges, helped focus attention on the phenomenon so typical of combinatorial structures: two seemingly very similar problems turn out in reality to be vastly different.
Since earning his PhD from Carnegie Mellon University in 1971, Manfred Padberg has made fundamental contributions to both the theoretical and the computational side of integer programming and combinatorial optimization. His early work on facets of the vertex packing polytope and their lifting, and on vertex adjacency on the set partitioning polytope, paved the way towards the wider use of polyhedral methods in solving integer programs. His joint work with Groetschel on facets of the traveling salesman polytope has served as a prototype of polyhedral analysis of difficult combinatorial problems. His characterization of perfect 0-1 matrices reinforced the already existing ties between graph theory and 0-1 programming.
Padberg is the originator and the main architect of the approach known as branch and cut. Concentrating on the traveling salesman problem as the main testbed, Padberg and Rinaldi successfully demonstrated that if cutting planes generated at various nodes of a search tree can be lifted so as to be valid everywhere, then interspersing them with branch and bound yields a procedure that vastly amplifies the power of either branch and bound or cutting planes by themselves. This work had and continues to have a lasting influence. One of the basic discoveries of the eighties in the realm of combinatorial optimization, arrived at by three different groups of researchers in the wake of the advent of the ellipsoid method for convex programming, was the equivalence of optimization and separation: Padberg and M. R. Rao formed one of these groups.
The winning publications were:
The paper, "Solving Large-Scale Zero-One Linear Programming Problems" by Ellis Johnson, Manfred Padberg, and Harlan Crowder, Operations Research, 31:5 (1983), pp. 803-834.
The book, Game Theory in the Social Sciences, by Martin Shubik, MIT Press, 1983.
The citation for the paper reads: "Zero-one linear programming is a very important problem in Operations Research. Efforts to solve large problems of this type have continued for over 20 years. However, success has been elusive, and problems with hundreds of zero-one variables and no special structure could usually not be solved in reasonable computation times.
"Ellis Johnson, Manfred Padberg, and Harlan Crowder have been important contributors to the field of integer programming for many years. In the paper "Solving Large-Scale Zero-One Linear Programming Problems" they combine recent results in problem preprocessing, constraint generation, and branch-and-bound techniques into an algorithm capable of solving problems with up to 2750 variables. Some of these results, particularly those on the knapsack cuts used, are due to the authors. They constructed a sophisticated computer implementation of this algorithm, using the IBM MPSX/370 and MIP/370 systems as building blocks. This system was applied to 10 large and difficult problems, all drawn from real-world industrial applications. An optimal solution was found and proved to be optimal in times ranging from a fraction of a minute to 54 minutes on an IBM 370/168.
"This paper demonstrates that the large body of research which describes facets of zero-one knapsack polytopes has significant computational as well as theoretical value. It makes an important contribution by noting that these cuts are likely to be particularly useful in sparse problems with general coefficients. The authors also develop effective computational strategies, and present a thorough series of tests showing the value of the various devices used.
"By integrating deep theoretical results, a sophisticated computer implementation, and realistic problems, this paper follows the best traditions of Operations Research. By showing that large problems can be solved exactly, it greatly expands the range of applications of integer programming, and should stimulate further work in this area. We therefore award it the 1983 Lanchester Prize."