Remembering George Dantzig
April 12, 2006
George Bernard Dantzig, 1914�2005. Photo by Edward Souza/Stanford News Service.
The life of George B. Dantzig, who died at the age of 90 on May 13, 2005, was both extraordinarily productive and extraordinarily influential. George was a towering, legendary figure who contributed to mathematics, operations research, economics, mathematical statistics, the solution of real-world problems, and theoretical computer science. To justify the brevity of this homage to him, we borrow from a clever "duality theory" comment made by Alan Hoffman at George's 80th birthday celebration: Because our admiration for George is unbounded, an adequate expression of it is infeasible. We accordingly summarize a few high points of George's career and life, emphasizing those of greatest interest to readers of SIAM News. More detailed discussions of George's accomplishments and activities are given in [2,3]; records of his vivid personality can be found in several published interviews and papers (e.g., [1,4�6]).
After receiving bachelor's (1936) and master's (1938) degrees, George took his first job, at the Bureau of Labor Statistics, where two life-changing events occurred: He learned about Wassily Leontief's 1932 input�output model of the U.S. economy (on which more later), and he reviewed a paper by Jerzy Neyman on mathematical statistics. In 1939, excited by Neyman's work, George enrolled in a PhD program at the University of California at Berkeley as Neyman's student. Probably the best-known incident in George's life, sometimes mistakenly considered an urban legend, took place at Berkeley: George solved two open problems in statistics, thinking that they were homework problems (see [3]). His work on these problems later formed the basis of his PhD thesis.
At this stage of his career, outside events caused a nonlinearity in his career path. Once the United States entered World War II in late 1941, George temporarily left his doctoral studies to work in the Combat Analysis Branch of the Statistical Control Division of the Air Force. In [5], he explains how his office collected data and helped other divisions prepare plans or proposed schedules, then called "programs," noting that he became an expert in doing "planning by hand techniques" (the only available computing devices being hand-operated mechanical calculators).
At the end of the war, he completed his PhD in one semester and returned to the Pentagon with the immediate goal of automating the planning process. George was also charged with developing mathematical models that could be used to formulate practical planning problems. In [5], he provides a memorable description of the then-prevailing approach to problem formulation:
Before linear programming and the simplex method were invented, it was not possible to . . . determine the best combination. Instead, all kinds of ground rules were invented, deemed by those in charge to be desirable characteristics for a program. . . . A typical example of a ground rule . . . was "Go ask General Arnold which alternative he prefers". A big program might contain hundreds of such highly subjective rules. And I said to myself "Well, we can't work with all these rules".
Deeply inspired by Leontief's steady-state input�output model, George had three key insights: (i) a more general framework was required that included changes over time, (ii) alternative activities should be possible, and (iii) an objective function, rather than ad hoc ground rules, was needed to make the problem computationally feasible. By mid-1947, George had formulated a model based on linear constraints with the novel feature of a linear objective function to replace the ground rules [4].
Next, because the Air Force generals expected real answers but George could find no one who knew how to compute them, he began to work on an algorithm. The simplex method arose from a result in his thesis on the existence of Lagrange multipliers for a certain semi-infinite linear program [4]. George credited his feeling that the simplex method might be efficient to his "column perspective" on the constraint matrix, in contrast to the pessimistic view from the row geometry that the method would inefficiently run "around the outside edges" [4]. (Because it was shown later that, for certain contrived problems, the simplex method can visit every one of an exponentially large number of vertices, we can only be thankful that George took the column perspective.) The rest is, of course, history, from the discovery via practical trials that the simplex method was indeed efficient through its continued success today, almost 60 years later.
George commented on several occasions (e.g., in [4]) on the remarkable flowering of ideas in 1947�49 that arose from three contemporaneous events: exposure of theoretical mathematicians and economists to real-world problems during World War II, the imminence of electronic computers with their promise for solving such problems, and the availability of support for the associated research. The creativity and excitement of those years are evident in the proceedings of the famous "Symposium Zero," the first of what became the International Symposia on Mathematical Programming. In 1949, Tjalling Koopmans organized a symposium called "Activity Analysis of Production and Allocation," where George was the sole author of four and a co-author of one of the 25 papers presented. It is a matter of historical interest that the then-unfamiliar term "linear programming" does not appear in the title of any of these papers, not even George's "Maximization of a Linear Function of Variables Subject to Linear Inequalities," in which he formally presented the simplex method. By 1951, when the proceedings were published, however, Koopmans (who had suggested the name in 1948) referred in his introduction to linear programming, albeit in quotation marks.
In 1952, George moved to the RAND Corporation, then a think tank for the Air Force, where he worked with an impressive array of other talent, including Ray Fulkerson, Selmer Johnson, and Philip Wolfe. George did foundational research while at RAND on a striking diversity of topics. It is no surprise that many of his publications involved aspects of linear programming, including duality theory, decomposition techniques, and the resolution of degeneracy. He also worked on network optimization, co-authoring along the way a classic 1954 paper with Fulkerson and Johnson on the traveling salesman problem that presented the solution to the then-largest TSP that had been solved exactly. Finally, he pursued his lifelong interest in linear programming under uncertainty, a part of stochastic optimization to which he devoted most of his later years.
Drawn to an academic career, George moved to UC Berkeley in 1960. Soon after his arrival, he established the Operations Research Center at the Richmond Field Station and began to build an active research group. While at Berkeley, he served as thesis adviser to eleven students who not only subsequently became leading figures in the growing fields of mathematical programming and operations research, but also (not by coincidence) served as proofreaders for his major, classic 1963 volume Linear Programming and Extensions. He made his final professional move in 1966, when he joined Stanford University's recently established Computer Science Department and Program in Operations Research (which became a department in 1967). During his 30 years at Stanford, George never ceased to display his characteristic versatility and energy.
As an educator, he supervised 41 Stanford doctoral students, whose dissertations covered a broad range of topics in operations research. A longstanding vision of George's, conceived soon after the war but unachievable then, was of solving systems-scale optimization problems. Beginning in the late 1960s, George gave conference talks about the idea of a "systems optimization laboratory" in which a critical mass of people and resources could develop models, methods, and software for solving complex real-world problems. He wrote two influential (and almost identical) papers, the second with multiple co-authors, on the need for a systems optimization laboratory [2,3]. Despite an unfavorable funding climate, he obtained external support for the proposed Systems Optimization Laboratory (SOL) at Stanford. Starting in the early 1970s, the Stanford SOL produced widely used methods and software and stimulated the founding of similar organizations around the world; it still exists today.
While at Stanford, George continued to be interested in economic models, working with colleagues on PILOT, an energy-focused model of the U.S. economy. Almost inevitably, the formulation of PILOT initially generated very large linear programs with staircase structure (harking back to George's earliest modeling experiences) and, later, large-scale economic equilibrium problems. With the arrival of Gerd Infanger in 1989, George returned essentially full-time to his beloved topic of stochastic optimization, or planning under uncertainty, which he described in [5] as "the real field we should all be working in," because "mathematical models act . . . [as if] we have a precise knowledge of what is happening, and we don't."
In addition to accomplishments in research and education, George diligently and loyally served his profession. He was president of the Institute of Management Sciences in 1966 and, in 1973�74, the first chairman of the Mathematical Programming Society. He was closely involved with the International Institute for Applied Systems Analysis in Austria, as well as with groups at the Technion in Israel and the Technical University of Link�ping in Sweden.
George received a variety of significant honors for his work. He was a member of the (U.S.) National Academies of Sciences and of Engineering, and the American Academy of Arts of Sciences, and he was the recipient of eight honorary doctorates. In 1975, he was awarded the National Medal of Science, the highest recognition of scientific achievement by the United States government.
Sadly, one major award that George did not receive was the Nobel Prize in Economics. (Kantorovich and Koopmans, who received the prize in 1975 for their work on linear programming, were among many who felt that George should have been a co-recipient, but they were unable to correct the omission.)
Much has been said and written, and rightly so, about George's exceptional qualities as a person. He was unfailingly warm, gracious, and kind to members of staff, students, colleagues, and visiting (or local) dignitaries. Gail Stein, his assistant for 22 years, recalls that, before leaving the office, he would always ask politely whether he needed to do anything more that day. When visitors from around the world appeared unexpectedly at his office door, insisting on meeting "the great Professor Dantzig," George displayed a degree of courtesy that less patient colleagues found astonishing. One of his most endearing qualities could be described to first order as "sweetness," but it was a sweetness combined with spice---liveliness, wit, and intelligence. Three further attributes apparent only to those who observed him in action were George's determination, quiet persistence, and effectiveness at getting things done.
Recognizing the impossibility of summing up George's life in a few words, we end with two quotations we consider revealing, one about him, one from him. Philip Wolfe, an early RAND colleague of George's, described his rare intellectual qualities in [6]:
George is a genius. . . . He has real originality. When he wades into a problem, he's unencumbered by the kind of baggage a lot of us have. He'll let the problem speak to him in its own language. . . . George has the new ideas.
We leave the last word to George, who said many times that he was happiest when his mathematical work led to the successful solution of practical problems [1]:
Because my mathematics has its origin in a real problem doesn't make it less interesting to me---just the other way around, I find it makes the puzzle I am working on all the more exciting. I get satisfaction out of knowing that I'm working on a relevant problem.
It has been very difficult to accept bidding farewell to this brilliant, iconic, and gentle man.
References
[1] D.J. Albers and C. Reid, An interview with George B. Dantzig: The father of linear programming, College Math. J., 17 (1986), 292�314.
[2] R.W. Cottle, George B. Dantzig: Operations research icon, Oper. Res., 53 (2005), 892�898.
[3] R.W. Cottle, George B. Dantzig: A legendary life in mathematical programming, Math. Prog. Series A, 105 (2006), 1�8.
[4] G.B. Dantzig, Linear programming, Oper. Res., 50 (2002), 42�47; http://www.informs.org/History/dantzig/LinearProgramming_article.pdf.
[5] I.J. Lustig, Interview with George B. Dantzig (2000); http://www.e-optimization.com/directory/trailblazers/dantzig.
[6] I.J. Lustig, Interview with Philip Wolfe (2000); http://www.e-optimization.com/directory/trailblazers/wolfe.
---Richard W. Cottle, Department of Management Science and Engineering, Stanford University, and Margaret H. Wright, Computer Science Department, Courant Institute of Mathematical Sciences, New York University.
