Past Awards
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."