This article was downloaded by: [132.248.67.

58] On: 22 November 2023, At: 09:20

Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
INFORMS is located in Maryland, USA

Operations Research
Publication details, including instructions for authors and subscription information:
http://pubsonline.informs.org

Linear Programming
George B. Dantzig,

To cite this article:

George B. Dantzig, (2002) Linear Programming. Operations Research 50(1):42-47. https://doi.org/10.1287/
opre.50.1.42.17798

Full terms and conditions of use: https://pubsonline.informs.org/Publications/Librarians-Portal/PubsOnLine-Terms-and-

Conditions

This article may be used only for the purposes of research, teaching, and/or private study. Commercial use
or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher
approval, unless otherwise noted. For more information, contact permissions@informs.org.

The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness
for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or
inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or
support of claims made of that product, publication, or service.

© 2002 INFORMS

Please scroll down for article—it is on subsequent pages

With 12,500 members from nearly 90 countries, INFORMS is the largest international association of operations research (O.R.)
and analytics professionals and students. INFORMS provides unique networking and learning opportunities for individual
professionals, and organizations of all types and sizes, to better understand and use O.R. and analytics tools and methods to
transform strategic visions and achieve better outcomes.
For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org
 LINEAR PROGRAMMING
GEORGE B. DANTZIG
Department of Management Science and Engineering, Stanford University, Stanford, California 94305-4023
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

The Story About How It Began: Some legends, a little the transportation problem was also overlooked until after
about its historical significance, and comments about where others in the late 1940’s and early 1950’s had independently
its many mathematical programming extensions may be rediscovered its properties.
headed. What seems to characterize the pre-1947 era was lack of
any interest in trying to optimize. T. Motzkin in his schol-

L inear programming can be viewed as part of a great

revolutionary development which has given mankind
the ability to state general goals and to lay out a path of
arly thesis written in 1936 cites only 42 papers on linear
inequality systems, none of which mentioned an objective
function.
detailed decisions to take in order to “best” achieve its goals The major influences of the pre-1947 era were Leon-
when faced with practical situations of great complexity. tief’s work on the Input-Output Model of the Economy
Our tools for doing this are ways to formulate real-world (1933), an important paper by von Neumann on Game The-
problems in detailed mathematical terms (models), tech- ory (1928), and another by him on steady economic growth
niques for solving the models (algorithms), and engines for (1937).
executing the steps of algorithms (computers and software). My own contributions grew out of my World War II
This ability began in 1947, shortly after World War II, experience in the Pentagon. During the war period (1941–
and has been keeping pace ever since with the extraordinary 45), I had become an expert on programming-planning
growth of computing power. So rapid has been the advance methods using desk calculators. In 1946 I was Mathemat-
in decision science that few remember the contributions of ical Advisor to the US Air Force Comptroller in the Pen-
the great pioneers that started it all. Some of their names tagon. I had just received my PhD (for research I had
are von Neumann, Kantorovich, Leontief, and Koopmans. done mostly before the war) and was looking for an aca-
The first two were famous mathematicians. The last three demic position that would pay better than a low offer I
received the Nobel Prize in economics. had received from Berkeley. In order to entice me to not
In the years from the time when it was first proposed take another job, my Pentagon colleagues, D. Hitchcock
in 1947 by the author (in connection with the planning and M. Wood, challenged me to see what I could do to
activities of the military), linear programming and its many mechanize the planning process. I was asked to find a way
extensions have come into wide use. In academic circles to more rapidly compute a time-staged deployment, train-
decision scientists (operations researchers and management ing and logistical supply program. In those days “mecha-
scientists), as well as numerical analysts, mathematicians, nizing” planning meant using analog devices or punch-card
and economists have written hundreds of books and an equipment. There were no electronic computers.
uncountable number of articles on the subject. Consistent with my training as a mathematician, I set
Curiously, in spite of its wide applicability today to out to formulate a model. I was fascinated by the work of
everyday problems, it was unknown prior to 1947. This Wassily Leontief who proposed in 1932 a large but simple
is not quite correct; there were some isolated exceptions. matrix structure which he called the Interindustry Input-
Fourier (of Fourier series fame) in 1823 and the well- Output Model of the American Economy. It was simple in
known Belgian mathematician de la Vallée Poussin in 1911 concept and could be implemented in sufficient detail to
each wrote a paper about it, but that was about it. Their be useful for practical planning. I greatly admired Leontief
work had as much influence on Post-1947 developments as for having taken the three steps necessary to achieve a suc-
would finding in an Egyptian tomb an electronic computer cessful application:
built in 3000 BC. Leonid Kantorovich’s remarkable 1939 1. Formulating the inter-industry model.
monograph on the subject was also neglected for ideolog- 2. Collecting the input data during the Great Depression.
ical reasons in the USSR. It was resurrected two decades 3. Convincing policy makers to use the output.
later after the major developments had already taken place Leontief received the Nobel Prize in 1976 for developing
in the West. An excellent paper by Hitchcock in 1941 on the input-output model.

Subject classification: Professional: comments on.

Area of review: Anniversary Issue (Special).

Operations Research © 2002 INFORMS 0030-364X/02/5001-0042 $05.00

Vol. 50, No. 1, January–February 2002, pp. 42–47 42 1526-5463 electronic ISSN
 Dantzig / 43
For the purpose I had in mind, however, I saw that Leon- disadvantages, that it would be impossible to compare all
tief’s model had to be generalized. His was a steady-state the cases and choose which among them would be the best.
model and what the Air Force wanted was a highly dynamic Invariably, man in the past has turned to a leader whose
model, one that could change over time. In Leontief’s ‘experience’ and ‘mature judgment’ would guide the way.
model there was a one-to-one correspondence between the Those in charge like to do this by issuing a series of ground
production processes and the items being produced by these rules (edicts) to be executed by those developing the plan.
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

processes. What was needed was a model with alternative This was the situation prior to 1946. In place of an
activities. Finally it had to be computable. Once the model explicit goal or objective function, there were a large num-
was formulated, there had to be a practical way to com- ber of ad hoc ground rules issued by those in authority to
pute what quantities of these activities to engage in that guide the selection. Without such rules, there would have
was consistent with their respective input-output character- been, in most cases, an astronomical number of feasible
istics and with given resources. This would be no mean solutions to choose from. Incidentally, “Expert System”
task since the military application had to be large scale, software which is very much in vogue today makes use of
with thousands of items and activities. this ad hoc ground-rule approach.
The activity analysis model I formulated would be All that I have related up to now about the early devel-
described today as a time-staged, dynamic linear program opment took place before the advent of the computer, more
with a staircase matrix structure. Initially there was no precisely, before in late 1946 we were aware that the com-
objective function; broad goals were never stated explic- puter was going to exist. But once we were aware, the com-
itly in those days because practical planners simply had no puter became vital to our mechanization of the planning
way to implement such a concept. Noncomputability was process. So vital was the computer, that our group arranged
the chief reason, I believe, for the total lack of interest in (in the late 1940’s) that the Pentagon fund the development
optimization prior to 1947. of computers.
To digress for a moment, I would like to say a few words
A simple example may serve to illustrate the fundamen-
about the electronic computer itself. To me, and I suppose
tal difficulty of finding a solution to a planning problem
to all of us, one of the most startling developments of all
once it is formulated. Consider the problem of assigning
time has been the penetration of the computer into almost
70 men to 70 jobs. Suppose a value or benefit vij would
every phase of human activity. Before a computer can be
result if the ith man is assigned to the jth job. An activity
intelligently used, a model must be formulated and good
consists in assigning the ith man to the jth job. The restric-
algorithms developed. To build a model, however, requires
tion are: (i) each man must be assigned a job (there are 70
the axiomatization of a subject matter field. In time this
such), and (ii) each job must be filled (also 70). The level
axiomatization gives rise to a whole new mathematical dis-
of an activity is either 1, meaning it will be used, or 0, cipline which is then studied for its own sake. Thus, with
meaning it will not. Thus there are 2 × 70 or 140 restric- each new penetration of the computer, a new science is
tions, 70 × 70 or 4900 activities with 4900 corresponding born.
0-1 decision variables xij . Unfortunately there are 70! dif- Von Neumann notes this tendency to axiomatize in his
ferent possible solutions or ways to make the assignments paper on The General and Logical Theory of Automata. In
xij . The problem is to compare the 70! solutions with one it he states that automata have been playing a continuously
another and to select the one which results in the largest increasing role in science. He goes on to say:
sum of benefits from the assignments.
Now 70! is a big number, greater than 10100 . Suppose we Automata have begun to invade certain parts of math-
ematics too, particularly but not exclusively mathemat-
had a computer capable of doing a million calculations per
ical physics or applied mathematics. The natural sys-
second available at the time of the big bang fifteen billion
tems (e.g., central nervous system) are of enormous
years ago. Would it have been able to look at all the 70! complexity and it is clearly necessary first to subdivide
combinations by the year 1990? The answer is no! Suppose what they represent into several parts which to a cer-
instead it could perform at nano-second speed and make tain extent are independent, elementary units. The prob-
1 billion complete assignments per second? The answer is lem then consists of understanding how these elements
still no. Even if the Earth were filled with such comput- are organized as a whole. It is the latter problem which
ers all working in parallel, the answer would still be neg- is likely to attract those who have the background and
ative. If, however, there were 1040 Earths circling the sun tastes of the mathematician or a logician. With this atti-
each filled solid with nanosecond speed computers all pro- tude, he will be inclined to forget the origins and then,
grammed in parallel from the time of the big bang until the after the process of axiomatization is complete, concen-
trate on the mathematical aspects.
Sun grows cold, then perhaps the answer might be, yes.
This easy-to-state example illustrates why up to 1947, By mid-1947, I had formulated a model which satisfacto-
and for the most part even to this day, a great gulf exists rily represented the technological relations usually encoun-
between man’s aspirations and his actions. Man may wish tered in practice. I decided that the ad hoc ground rules
to state his wants in complex situations in terms of a gen- had to be discarded and replaced by an explicit objective
eral objective to be optimized but there are so many dif- function. I formulated the planning problem in mathemat-
ferent ways to go about it, each with its advantages and ical terms using a set of axioms. The axioms concerned
 44 / Dantzig
the relations between two kinds of sets: the first was the leading mathematician in the world. On October 3, 1947, 1
set of items being produced or consumed and the second, met him for the first time at the Institute Advanced Study
the set of activities or production processes in which these at Princeton.
items would be inputted or outputted in fixed proportions John von Neumann made a strong impression on every-
providing these proportions are non-negative multiples of one. People came to him for help with their problems
each other. The resulting system to be solved was the min- because of his great insight. In the initial stages of the
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

imization of a linear form subject to linear equations and development of a new field like linear programming, atomic
inequalities. The use (at the time it was proposed) of a lin- physics, computers, or whatever, his advice proved invalu-
ear form as the objective function to be extremized was a able. After these fields were developed in greater depth,
novel feature of the model. however, it became more difficult for him to make the same
Now came the nontrivial question: Can one solve such spectacular contributions. I guess everyone has a finite
systems? At first I assumed the economists had worked capacity, and Johnny was no exception.
on this problem since it was the problem of allocation of I remember trying to describe to von Neumann (as
scarce resources. I visited T. C. Koopmans in June 1947 at I would to an ordinary mortal) the Air Force problem.
the Cowles Foundation (which at that time was at the Uni- I began with the formulation of the linear programming
versity of Chicago) to learn what I could from the mathe- model in terms of activities and items, etc. He did some-
matical economists. Koopmans became quite excited. Dur- thing which I believe was uncharacteristic of him. “Get to
ing World War II, he had worked for the Allied Shipping the point,” he snapped at me impatiently. Having at times a
Board on a transportation model and so had the theoretical somewhat low kindling point, I said to myself, “OK, if he
as well as the practical planning background necessary to wants a quickie, then that’s what he’ll get.” In under one
appreciate what I was presenting. He saw immediately the minute I slapped on the blackboard a geometric and alge-
implications for general economic planning. From that time braic version of the problem. Von Neumann stood up and
on, Koopmans took the lead in bringing the potentialities of said, “Oh that!” Then, for the next hour and a half, he pro-
linear programming models to the attention of other young ceeded to give me a lecture on the mathematical theory of
economists who were just starting their careers. Some of linear programs.
their names were Kenneth Arrow, Paul Samuelson, Herbert At one point, seeing me sitting there with my eyes pop-
Simon, Robert Dorfman, Leonid Hurwricz, and Herbert ping and my mouth open (after all I had searched the liter-
Scarf, to name but a few. Some thirty to forty years later ature and found nothing), von Neumann said:
four of them received the Nobel Prize for their research. I don’t want you to think I am pulling all this out of my
Seeing that economists did not have a method of solu- sleeve on the spur of the moment like a magician. I have
tion, I next decided to try my own luck at finding an recently completed a book with Oscar Morgenstern on
algorithm. I owe a great debt to Jerzy Neyman, the lead- the theory of games. What I am doing is conjecturing
ing mathematical statistician of his day, who guided my that the two problems are equivalent. The theory that I
graduate work at Berkeley. My thesis was on two famous am outlining is an analogue to the one we have devel-
unsolved problems in mathematical statistics which I mis- oped for games.
takenly thought were a homework assignment and solved. Thus I learned about Farkas’ Lemma, and about Dual-
One of the results, published jointly with Abraham Wald, ity for the first time. Von Neumann promised to give my
was on the Neyman-Pearson Lemma. In today’s terminol- computational problem some thought and to contact me in
ogy, this part of my thesis was on the existence of Lagrange a few weeks which he did. He proposed an iterative non-
multipliers (or dual variables) for a semi-infinite linear pro- linear scheme. Later Alan Hoffman and his group at the
gram whose variables were bounded between zero and one Bureau of Standards (around 1952) tried it out on a num-
and satisfied linear constraints expressed in the form of ber of test problems. They also compared it to the simplex
Lebesgue integrals. There was also a linear objective to be method and with some proposals of T. Motzkin. The sim-
extremized. plex method came out a clear winner.
Luckily the particular geometry used in my thesis was As a result of another visit in June 1948, I met Albert
the one associated with the columns of the matrix instead Tucker, who later became head of the Mathematics depart-
of its rows. This column geometry gave me the insight ment at Princeton. Soon Tucker and his students Harold
which led me to believe that the simplex method would be Kuhn and David Gale and others like Lloyd Shapley began
a very efficient solution technique. I earlier had rejected their historic work on game theory, nonlinear programming
the method when I viewed it in the row geometry because and duality theory. The Princeton group became the focal
running around the outside edges seemed so unpromising. point among mathematicians doing research in these fields.
I proposed the simplex method in the summer 1947. But The early days were full of intense excitement. Scien-
it took nearly a year before my colleagues and I in the tists, free at last from war time pressures, entered the post-
Pentagon realized just how powerful the method really was. war period hungry for new areas of research. The com-
In the meantime, I decided to consult with the great, Johnny puter came on the scene at just the right time. Economists
von Neumann to see what he could suggest in the way and mathematicians were intrigued with the possibility that
of solution techniques. He was considered by many as the the fundamental problem of optimal allocation of scarce
 Dantzig / 45
resources could be numerically solved. Not too long after algorithm include a way of avoiding degeneracy. Therefore,
my first meeting with Tucker there was a meeting of much of the early research around 1950 by Alex Orden,
the Econometric Society in Wisconsin attended by well- Philip Wolfe and myself at the Pentagon and by J. H.
known statisticians and mathematicians like Hotelling and Edmonson as a class exercise in 1951 and by A. Charnes in
von Neumann, and economists like Koopmans. I was a 1952 was concerned with what to do if a degenerate solu-
young unknown and I remember how frightened I was with tion is encountered.
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

the idea of presenting for the first time to such a distin- In the early 1950’s many areas which we collectively
guished audience the concept of linear programming. call Mathematical Programming began to emerge. These
After my talk, the chairman called for discussion. For subfields grew rapidly with linear programming playing a
a moment there was the usual dead silence; then a hand fundamental role in their development. A few words will
was raised. It was Hotelling’s. I must hasten to explain now be said about each of these.
that Hotelling was fat. He used to love to swim in the
ocean and when he did, it is said that the level of the ocean Nonlinear Programming began around 1951 with the
rose perceptibly. This huge whale of a man stood up in famous Karush-Kuhn-Tucker Conditions which are related
the back of the room, his expressive fat face took on one to the Fritz-John Conditions (1948). In 1954, Ragnar Frisch
of those all-knowing smiles we all know so well. He said: (who later received the first Nobel prize in economics) pro-
“But we all know the world is nonlinear.” Having uttered posed a nonlinear interior point method for solving lin-
this devastating criticism of my model, he majestically sat ear programs. Earlier proposals such as those of von Neu-
down. And there I was, a virtual unknown, frantically trying mann and Motzkin can also be viewed as interior methods.
to compose a proper reply. Later in the 1960’s, G. Zoutendijk, T. Rockafellar, P. Wolfe,
Suddenly another hand in the audience was raised. It was R. Cottle, Fiacco and McCormick, and others developed the
von Neumann. “Mr. Chairman, Mr. Chairman,” he said, theory of nonlinear programming and extended the notions
“if the speaker doesn’t mind, I would like to reply for of duality.
him.” Naturally I agreed. Von Neumann said: “The speaker
titled his talk ‘linear programming’ and carefully stated his Commercial Applications were begun in 1952 by
axioms. If you have an application that satisfies the axioms, Charnes, Cooper and Mellon with their (now classical)
well use it. If it does not, then don’t,” and he sat down. optimal blending of petroleum products to make gasoline.
In the final analysis, of course, Hotelling was right. The Applications quickly spread to other commercial areas and
world is highly nonlinear. Fortunately systems of linear soon eclipsed the military applications which started the
inequalities (as opposed to equalities) permit us to approx- field.
imate most of the kinds of nonlinear relations encountered Software—The Role of Orchard-Hays. In 1954, William
in practical planning. Orchard-Hays of the Rand Corporation, wrote the first
In 1949, exactly two years from the time the Lin- commercial-grade software for solving linear programs.
ear programming was first conceived, the first confer- Many theoretical ideas such as ways to compact the inverse,
ence (sometimes referred to as the Zero Symposium) on take advantage of sparsity, and guarantee numerical sta-
mathematical programming was held at the University of
bility were first implemented in his codes. As a result
Chicago. Tjalling Koopmans, the organizer, later titled the
his software ideas dominated the field for many decades
proceedings of the conference, Activity Analysis of Produc-
and made commercial applications possible. The impor-
tion and Allocation. Economists like Koopmans, Kenneth
tance of Orchard-Hays’ contributions cannot be overstated
Arrow, Paul Samuelson, Leonid Hurwitz, Robert Dorfman,
for it stimulated the entire development of the field and
Nicholos Georgescu-Roegen, and Herbert Simon; math-
transformed linear programming and its extensions from an
ematicians like Albert Tucker, Harold Kuhn, and David
interesting mathematical theory into a powerful tool that
Gale; and Air Force types like Marshall Wood, Murray
changed the way practical planning was done.
Geisler, and myself all made contributions.
The advent or rather the promise that the electronic com- Network Flow Theory began to evolve in the early
puter would exist soon, the exposure of theoretical mathe- 1950’s. Flood, Ford and Fulkerson in 1954, Hoffman and
maticians and economists to real problems during the war, Kuhn in 1956 developed its connections to graph theory.
the interest in mechanizing the planning process, and last Recent research on combinatorial optimization benefited
but not least the availability of money for such applied from this early research.
research all converged during the period 1947–1949. The
time was ripe. The research accomplished in exactly two Large-Scale Methods began in 1955 with my paper
years is, in my opinion, one of the remarkable events of “Upper Bounds, Block Triangular Systems, and Secondary
history. The proceedings of the conference remains to this Constraints.” In 1959-60 Wolfe and I published our papers
very day an important basic reference, a classic! on the Decomposition Principle. Its dual form was discov-
The simplex method turned out to be a powerful theoret- ered by Benders in 1962 and first applied to the solution
ical tool for proving theorems as well as a powerful com- of mixed integer programs. It is now extensively used to
putational tool. To prove theorems it is essential that the solve stochastic programs.
 46 / Dantzig
Stochastic Programming began in 1955 with my paper Polynomial-Time Algorithms. For a long time it was not
“Linear Programming under Uncertainty” (an approach known whether or not linear programs belonged to a non-
which has been greatly extended by R. J.-B. Wets in polynomial class called “hard” (such as the one the trav-
the 1960’s and J. R. Birge in the 1980’s). Independently, eling salesman problem belongs to) or to an “easy” poly-
at almost the same time in 1955, E. M. L. Beale pro- nomial class (like the one that the shortest path problem
posed ways to solve stochastic programs. Important con- belongs to). In 1970, Victor Klee and George Minty created
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

tributions to this field have been made by A. Charnes an example that showed that the classical simplex algorithm
and W. W. Cooper in the late 1950’s using chance con- would require an exponential number of steps to solve a
straints, i.e., constraints which hold with a stated proba- worst-case linear program. In 1978, the Russian mathemati-
bility. Stochastic programming is one of the most promis- cian L. G. Khachian developed a polynomial-time algo-
ing fields for future research, one closely tied to large- rithm for solving linear programs. It is an interior method
scale methods. One approach that the author, Peter Glynn using ellipsoids inscribed in the feasible region. He proved
and Gerd Inflanger investigated (1990), combines Benders’ that the computing time is guaranteed to be less that a poly-
decomposition principle, with ideas based on importance nomial expression in the dimensions of the problem and
sampling and the use of parallel processors. the number of digits of input data. Although polynomial,
Integer Programming began in 1958 by R. E. Gomory. the bound he established turned out to be too high for his
Unlike the earlier work on the traveling salesman problem algorithm to be used to solve practical problems.
by D. R. Fulkerson, S. M. Johnson and Dantzig, Gomory Karmarkar’s algorithm (1984) was an important
showed how to systematically generate the ‘cutting’ planes. improvement on the theoretical result of Khachian that a
Cuts are extra necessary conditions which when added to linear program can be solved in polynomial time. Moreover
an existing system of inequalities guarantee that the opti- his algorithm turned out to be one which could be used to
mization solution will solve in integers. Ellis Johnson of solve practical linear programs. At the present time (1990),
IBM extended the ideas of Gomory. Egon Balas and many interior algorithms are in open competition with variants of
others have developed clever elimination schemes for solv- the simplex method. It appears likely that commercial soft-
ing 0-1 covering problems. Branch-and-bound has turned ware for solving linear programs will eventually combine
out to be one of the most successful ways to solve practi- pivot type moves used in the simplex methods with interior
cal integer programs. The most efficient techniques appear type moves.
to be those which combine cutting planes with branch-and-
bound. ORIGINS OF CERTAIN TERMS
Complementary Pivot Theory was started around Here are some stories about how various linear program-
1962–63 by Richard Cottle and Dantzig and greatly ming terms arose. The military refer to their various plans
extended by Cottle. It was an outgrowth of Wolfe’s method or proposed schedules of training, logistical supply and
for solving quadratic programs. In 1964 Lemke and How- deployment of combat units as a program. When I first ana-
son applied the algorithm to bimatrix games. In 1965 lyzed the Air Force planning problem and saw that it could
Lemke extended the approach to other nonconvex pro- be formulated as a system of linear inequalities, I called
grams. Lemke’s results represent a historic breakthrough my paper Programming in a Linear Structure. Note that the
into the nonconvex domain. In the 1970’s, Scarf, Kuhn, and term ‘program’ was used for linear programs long before
Eaves extended this approach once again to the solving of it was used as the set of instructions used by a computer.
fixed point problems. In the early days, these instructions were called codes.
Computational Complexity. Many classes of computa- In the summer of 1948, Koopmans and I visited the
tional problems, although they arise from different sources Rand Corporation. One day we took a stroll along the
and appear to have quite different mathematical statements Santa Monica beach. Koopmans said: “Why not shorten
can be “reduced” to one another by a sequence of not-too- ‘Programming in a Linear Structure’ to ‘Linear Program-
costly computational steps. Those that can be so reduced ming’?” I replied: “That’s it! From now on that will be its
are said to belong to the same equivalence class. This name.” Later that day I gave a talk at Rand, entitled “Linear
means that an algorithm that can solve one member of a Programming”; years later Tucker shortened it to Linear
class can be modified to solve any other in the same equiv- Program.
alence class. The computational complexity of an equiv- The term Mathematical Programming is due to Robert
alence class is a quantity which measures the amount of Dorfman of Harvard, who felt as early as 1949 that the
computational effort required to solve the most difficult term Linear Programming was too restrictive.
problem belonging to the class, i.e., its worst case. A non- The term simplex method arose out of a discussion
polynomial algorithm would be one which requires in the with T. Motzkin who felt that the approach that I was
worst case a number of steps not less than some exponen- using, when viewed in the geometry of the columns,
tial expression like Lnm
n!
100n , where n and m refer to was best described as a movement from one simplex
the row and column dimensions of the problem and L to to a neighboring one. Mathematical programming is also
the number of bits needed to store the input data. responsible for many terms which are now standard in
 Dantzig / 47
mathematical literature, terms like Arg Min, Arg Max, taking place in many countries. This active and difficult
Lexico-Max, Lexico-Min. The term dual is an old math- field has already solved some important long term plan-
ematical term. But surprisingly the term primal is new ning problems. I believe that progress depends on ideas
and was proposed by my father Tobias Dantzig around drawn from many fields. For example, our group at Stan-
1954 after William Orchard-Hays stated the need for a ford is working on a solution method, which combines
word to call the original problem whose dual was such the Nested Decomposition Principle, Importance Sampling,
Downloaded from informs.org by [132.248.67.58] on 22 November 2023, at 09:20 . For personal use only, all rights reserved.

and such. and the use of parallel processors.

Prior to linear programming it was not practical to
SUMMARY OF MY OWN explicitly state general goals and so objectives were often
EARLY CONTRIBUTIONS confused with the ground rules for the solution. Ask a mil-
itary commander what the goal is and he would say, “The
If I were asked to summarize my early and perhaps my
goal is to win the war.” Upon being pressed to be more
most important contributions to linear programming, I
explicit, a Navy man might say, “The way to win the war
would say they are three:
is to build battleships,” or, if he is an Air Force general,
(1) Recognizing (as a result of my wartime years as
he might say, “The way to win is to build a great fleet of
a practical program planner) that most practical planning
bombers.” Thus the means to attain the objective becomes
relations could be reformulated as a system of linear
the objective in itself, which in turn spawns new ground
inequalities.
rules as to how to go about attaining the means such as
(2) Replacing the set of ground rules for selecting good
how best to go about building bombers. These means in
plans by an objective function. (Ground rules at best are
turn become confused with goals.
only a means for carrying out the objective, not the objec-
From 1947 on, the notion of what is meant by a goal
tive itself.)
has been adjusting to our increasing ability to solve com-
(3) Inventing the simplex method which transformed the
plex problems. As we near the end of the 20th Century,
rather unsophisticated linear-programming model of the
planners are becoming more and more aware that it is pos-
economy into a basic tool for practical planning of large
sible to optimize a specific objective while, at the same
complex systems.
time, hedging against a great variety of unfavorable contin-
The tremendous power of the simplex method is a con-
gencies which might happen and taking advantage of any
stant surprise to me. To solve by brute force the assignment
favorable opportunity that might arise.
problem (which I mentioned earlier) would require a solar
The ability to state general objectives and then be able
system full of nano-second electronic computers running
to find optimal policy solutions to practical decision prob-
from the time of the big bang until the time the universe
lems of great complexity is the revolutionary development
grows cold to scan all the permutations in order to select
I spoke of earlier. We have come a long way to achieving
the one which is best. Yet it takes only a moment to find
this goal but much work remains to be done, particularly in
the optimum solution using a personal computer and stan-
the area of uncertainty. The final test will come when we
dard simplex or interior method software.
can solve the practical problems which originated the field
In retrospect it is interesting to note that the original
back in 1947.
problem that started my research is still outstanding—
namely the problem of planning or scheduling dynami-
cally over time, particularly planning dynamically under This article originally appeared in History of Mathemati-
uncertainty. If such a problem could be successfully solved cal Programming: A Collection of Personal Reminiscences,
it could (eventually through better planning) contribute to 1991, J. K. Lenstra, A. H. G. Rinnooy Kan, and A. Schrij-
the well-being and stability of the world. ver (eds.), Elsevier Science Publishers B.V., Amsterdam,
By 1990, stochastic programming has become a very The Netherlands. Copyright is held by the author and is
exciting field of research and application with research reprinted here with his permission.