Systems Optimization Laboratory
Stanford, CA 94305-4026 USA
Professor George Dantzig:
Linear Programming Founder Turns 80
SIAM News, November 1994
In spite of impressive developments in computational optimization in the
last 20 years, including the rapid advance of interior point methods, the
simplex method, invented by George B. Dantzig in 1947, has stood the test
of time quite remarkably: It is still the pre-eminent tool for almost all
applications of linear programming.
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
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.