Professor George Dantzig:
Linear Programming Founder Turns 80

SIAM News, November 1994

Dantzig, who turns 80 on November 8, is generally regarded as one of the three founders of linear programming, along with von Neumann and Kantorovich. Through his research in mathematical theory, computation, economic analysis, and applications to industrial problems, he has contributed more than any other researcher to the remarkable development of linear programming.

Dantzig's work has been recognized by numerous honors, among them the National Medal of Science (1975), the John von Neumann Theory Prize of the Operations Research Society of America and the Institute of Management Sciences (1974), and membership in the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Sciences. But he has his own basis for judging his work: "The final test of any theory," he said in the opening sentence of his 1963 book Linear Programming and Extensions, "is its capacity to solve the problems which originated it."

Linear programming and its offspring (such as nonlinear constrained optimization and integer programming) have come of age and have demonstrably passed this test, and they are fundamentally affecting the economic practice of organizations and management. Computer scientist Laszlo Lovasz said in 1980, "If one would take statistics about which mathematical problem is using up most of the computer time in the world, then (not including database handling problems like sorting and searching) the answer would probably be linear programming." That same year, Eugene Lawler of Berkeley offered the following summary: "It [linear programming] is used to allocate resources, plan production, schedule workers, plan investment portfolios and formulate marketing (and military) strategies. The versatility and economic impact of linear programming in today's industrial world is truly awesome."

Dantzig's own assessment, set forth in the chapter he contributed to the History of Mathematical Programming: A Collection of Personal Reminiscences, is characteristically modest. In his words: "The tremendous power of the simplex method is a constant surprise to me." Citing the simple example of an assignment problem (70 people to 70 jobs) and the impossibly vast computing power that would be required to scan all the permutations to select the one that is best, he observed that "it takes only a moment to find the optimum solution using a personal computer and standard simplex or interior point method software."

Dantzig's unassuming nature and complete lack of pretension are the subject of countless anecdotes recounted by friends and colleagues. One researcher in optimization contributed his favorite George Dantzig story to SIAM News: About 15 years ago, having just completed his PhD, he found himself at a loss for words when, on meeting Dantzig for the first time, Dantzig enthusiasticaly responded to the introduction, "I've heard so much about you!"

"In retrospect," Dantzig wrote in the 1991 history book, "it is interesting to note that the original problem that started my research is still outstanding -- namely the problem of planning or scheduling dynamically over time, particularly planning dynamically under uncertainty. If such a problem could be successfully solved it could eventually through better planning contribute to the well-being and stability of the world."

The nature of that original problem is also detailed in the book. Dantzig's contributions, he explained, grew out of his experience in the Pentagon during World War II, when he had become an expert on programming -- planning methods done with desk calculators. In 1946, as mathematical adviser to the U.S. Air Force Comptroller, he was challenged by his Pentagon colleagues to see what he could do to mechanize the planning process, "to more rapidly compute a time-staged deployment, training and logistical supply program." In those pre-electronic computer days, mechanization meant using analog devices or punch-card machines. ("Program" at that time was a military term that referred not to the instruction used by a computer to solve problems, which were then called "codes," but rather to plans or proposed schedules for training, logistical supply, or deployment of combat units. The somewhat confusing name "linear programming," Dantzig explained in the book, is based on this military definition of "program.")

The large-scale "activity analysis" model he developed, Dantzig said, would be described today as a time-staged dynamic linear program with a staircase matrix structure. In those days, he explained, "There was no objective function" [italics his]. Lacking the power of electronic computers, practical planners at the time had no way to implement such a concept. In fact, summarizing his contributions to linear programming, Dantzig listed the substitution of an explicit objective function for a set of ad hoc rules, along with two others -- the recognition that practical planning relations could be reformulated as a system of linear inequalities and the invention of the simplex method.

As viewed by his colleagues, the list of Dantzig's professional accomplishments extends beyond linear programming and the simplex method to decomposition theory, sensitivity analysis, complementary pivot methods, large-scale optimization, nonlinear programming, and programming under uncertainty. His research in linear programming (and the related areas of nonlinear optimization, integer programming, and optimization under uncertainty) has had a fundamental impact on the consequential development of operations research as a discipline. Inasmuch as operations research is defined by the use of analytic tools to improve decision-making, operations research as a discipline could not exist without the use of formal optimization models as mental constructs, and the actual solution of models in a practical setting.

Dantzig is so well known to the optimization community that in 1991, when the editors of the SIAM Journal on Optimization decided to dedicate the first issue to him, they needed very few words: "The first issue of the SIAM Journal on Optimization is dedicated to George Dantzig who has been so influential in the development of optimization."

Since 1979, with the Mathematical Programming Society, SIAM has also honored Dantzig by awarding the George B. Dantzig Prize. The prize, which recognizes original research that has had a major impact on the field of mathematical programming, was awarded for the first time in 1982, to Michael Powell and R. T. Rockafellar. Since then it has been awarded every three years; the recipients are Ellis Johnson and Manfred Padberg (1985), Michael J. Todd (1988), Martin Grotschel and Arkady S. Nemirovsky (1991), and Claude Lemarechal and Roger J. B. Wets (1994). On the occasion of Dantzig's 80th birthday, many of his friends and colleagues have made contributions to the prize fund. For others wishing to do so, checks should be made payable to the SIAM-Dantzig Prize Fund and sent to Richard W. Cottle (Department of Operations Research, Stanford University, Stanford, CA 94305-4022).

Robert Freund of M.I.T. contributed extensively to this article.