Interviewer: Irv Lustig
During the Second World War
Lustig: What did you do in the Pentagon?
Dantzig: During World War II, I was in charge of the Combat Analysis Branch of the Statistical Control Division of the United States Airforces. My office collected data about sorties flown, bombs dropped, aircraft lost... I also helped other divisions of the Air Staff prepare plans called "programs".
Lustig: What kind of planning were they doing by hand at that time?
Dantzig: If you want to know the war effort was an enormous effort taking place in a period of about four years. At the end of the war, it was essentially doing the same thing as planning a whole country. Done on an enormous scale. We developed all kinds of special techniques for doing it by hand.
Lustig: So, the Air Staff was doing the planning of different operations pertaining to the deployment of the combat forces, the detailed logistics of supply and the training of personnel?
Dantzig: Yes, everything was planned in greatest detail: all the nuts and bolts, the procurement of airplanes, the detailed manufacture of everything. There were hundreds of thousands of different kinds of material goods and perhaps fifty thousand specialties of people. My office collected data about the air combat such as the number of sorties flown, the tons of bombs dropped, attrition rates. I also became a skilled expert on doing planning by hand techniques.
Just After the War
Dantzig: At the end of the war, everything began to dissolve. People went their own ways, which meant getting out of the military and going back to civilian life. I too was looking for a job after I finished my Ph.D. I was looking for an academic job.
When the war ended, I went out to Berkeley to finish up my PhD. That was one semester, and then I came back to the Pentagon. Berkeley made me an offer, but I didn't like it because it was too small. Or, to be more exact, my wife did not like it. It was a grand salary of fourteen hundred dollars a year. She did not see how we could live on that with our child David.
I returned to the Pentagon and began to look around for another job. The date was June 1946. I was in the market for a better paying job at a University. I received a number of offers. My colleagues at the Pentagon wanted me to stay on and were busy looking for something that I might do to keep me in, to keep me interested. The idea they came up with was to mechanize the planning process. Before that, in the Pentagon, it was all done by hand.
Lustig: So you decided to stay on at the Defense Department and to work on mechanizing the planning process. One of your first papers was entitled "Programming in a Linear Structure". What were the mathematical structures that you had in mind at that time?
Dantzig: The mathematical structures were what we called later linear programs. Our immediate goal was to speed up what was being done by hand.
Lustig: In June 1947 you came up with the linear programming model and then you proposed in August 1947 the simplex method of solution, correct?
Dantzig: Yes.
Lustig: How long did it take before the military was able to realize some of the benefits of the models and the algorithms that you were proposing?
Dantzig: About eight years. You must remember in 1947, computers were just beginning to be built and it was not until 1955 that they began to be reliable. We implemented around 1950 a mathematical model which we called the "Triangular Model" which was solved using punch card machinery.
Lustig: Can you tell us about the first applications of linear programming that were solved by hand?
Dantzig: There were two.
There was something called the Berlin Airlift. At the time, we were having trouble with the Russians, and they had blockaded Berlin. So the American and Allied forces, other than Russia, were like prisoners in the Middle of Berlin. The only way that the supplies were coming into Berlin at all was via airplanes. The United States and Britain had control of an airfield in the Berlin area, and we were flying in supplies. There was one program that we invented called the "Berlin Airlift", which set up the logistics of it, and we solved that problem.
We also solved Stigler's "Minimum Cost Diet Problem". The hand calculations were done by a team under the supervision of Jack Laderman at the U.S. National Bureau of Standards.
Symposium Zero
Lustig: How did the series of the Symposia on Mathematical Programming get started?
Dantzig: The various Symposia on Mathematical Programming started in the 1950's and were numbered 1, 2, 3, ... But the one that really started the series was a remarkable conference organized by Tjalling Koopmans. It was in 1949 and was entitled "Activity Analysis of Production and Allocation".
People who were involved in the war effort had some kind of job but not what they really wanted to do. So they were looking for a new outlet, something different. Koopmans was an economist at the University of Chicago Coast Foundation. He was very influential and introduced a lot of people to the whole field. For example, Ken Arrow, who was one of the first people to get the Nobel Prize in Economics.
In fact, all the young economists who presented papers at this conference - Tjalling Koopmans, Kenneth Arrow, Herb Simon, Paul Samuelson - later received the Nobel Prize in Economics.
What was most remarkable about the 1949 conference is that it took place only two years after I first formulated the linear programming problem. Two years afterwards we had a conference that produced these proceedings. And you can read this book, today, it is just as up to date. Because in those days, everybody who was involved in the war effort was hungry to do something. Some realized this was a new field with great potential.
[Download the Proceedings at the Cowles Foundation website]
Emergence of Computers
Lustig: Once the simplex method was developed, was it immediately used to solve some planning problems by hand?
Dantzig: Yes, two problems, the Berlin Airlift and the Minimum Cost diet problem. You've got to remember there wasn't any computers.
Lustig: Right!
Dantzig: It was a great idea, and everybody immediately saw it had great potential. So we went through the game of developing the whole planning process using computers, and in fact, we were responsible for actually getting money from the airforce and military to the manufacturers to build computers to research on them.
Lustig: We always try to look for connections between the early developments of computers with the first Univac built at the University of Pennsylvania and the development of linear programming. Can you describe some of those connections?
Dantzig: If my memory serves me right, ENIAC, one of the first electronic computers was built by Eckert and Mauchly at the University of Pennsylvania and then moved to the Army Aberdeen Proving Grounds in Maryland. It was built before linear programming was invented. UNIVAC also was built by Eckert and Mauchly a few years after linear programming was invented.
Lustig: Were some of the early computers built for the purpose of solving linear programs?
Dantzig: Yes. And of course they were also built for other people with different applications in mind. If you ask the question if we visualized that the computer would evolve as it did, we all saw that the computer was meant to be something, and in our minds eye, the computer wasn't much different than it was today. It seems hard to believe!
Lustig: That is hard to believe!
Dantzig: Except we did not visualize their present phenomenal speed.
Father of Linear Programming
Dantzig: I can tell you how I became the father of linear programming. In the very early days, I was invited to Japan. When I came off the plane, the people who were my hosts kept looking for me because they could not find me. They had envisioned the one who originated linear programming would be an old man... At this stage, I was still very young! So that's the way I became the father of linear programming.
Lustig: What is the origin of the word programming? Is it a word used a lot by the military? Does it have a different meaning than programming a computer?
Dantzig:
It is a word used by the military for a plan, a schedule, or in general for a program of actions. This is exactly what it means for computers: a program of actions for the computer to execute.
Lustig: Because of the wide use of computers and computer programming, people don't understand that we are talking about a different kind of programming when we speak of mathematical programming.
Dantzig: That's right, the word programming was used in linear programming. Linear programming was in vogue before programming in computers. Before, they called it coding, coding for the computers. The list of instructions to be executed by a computer was first called a "code". The military refer to their plans as "programs".
Lustig: How would you describe a linear program?
Dantzig: Mathematically a linear program is a system of linear inequalities, plus a linear form to be optimized.
The Economists and Mathematical Programming
Lustig: What is the difference between linear programming and mathematical programming?
Dantzig: Well, mathematical programming is more general. One of the people that was at the Pentagon in those days was a sharp economist, and eventually a well-known Harvard professor. That was Robert Dorfman. Bob Dorfman was after me to use the term mathematical programming, not linear programming. I felt that the whole way in which economists had set up their models was far, far more general than linear programming. Linear programming was a special case and that in order for the field to progress, we should stick to the simpler term linear programming. So he was after me right from the very beginning: why not generalize it? Why not use a more general term, mathematical programming? I felt greater progress would be made if we stuck to linear programming and later when the field matured generalize it to mathematical programming.
Optimization and Rules
Lustig: How do you explain optimization to people who haven't heard of it?
Dantzig: I would illustrate the concept using simple examples such as the diet problem or the blending of crude oils to make high-octane gasoline.
Lustig: What do you think has held optimization back from becoming more popular?
Dantzig: It is a technical idea that needs to be demonstrated over and over again. We need to show that firms that use it make more money than those who don't.
Lustig: Can you recall when optimization started to become used as a word in the field?
Dantzig: From the very beginning of linear programming in 1947, terms like maximizing, minimizing, extremizing, optimizing a linear form and optimizing a linear program were used.
The whole idea of objective function, which of course optimization applies, was not known prior to linear programming. In other words, the idea of optimizing something was something that nobody could do, because nobody tried to optimize. So while you are very happy with it and say it's a very familiar term, optimization just meant doing it better than somebody else. And the whole concept of getting the optimum solution just didn't exist. So my introducing the whole idea of optimization in the early days was novel.
Lustig: I understand that while programming the war effort in World War II was done on a vast scale, the term optimization as a word was never used. What was used instead?
Dantzig: A program can be thought of as a set of blocks, or activities, of different shapes that can to be fitted together according to certain rules, or mass balance constraints. Usually these can be combined in many different ways, some more, some less desirable than other combinations. Before linear programming and the simplex method were invented, it was not possible to computationally determine the best combination such as finding the program that maximizes the number of sorties flown. Instead, all kinds of ground rules were invented deemed by those in charge to be desirable characteristics for a program to have. A typical example of a ground rule that might have been used 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." Because what it meant was that you set up a plan. Then you have so many rules that you have to get some resolution of these rules and statements of what they were. To do this, you had to be running to the general, and to his assistants and asking them all kinds of questions.
Lustig: Name some of your most important early contributions.
Dantzig: The first was the recognition that most practical planning problems could be reformulated mathematically as finding a solution to a system of linear inequalities. My second contribution was recognizing that the plethora of ground rules could be eliminated and replaced by a general objective function to be optimized. My third contribution was the invention of the simplex method of solution.
Lustig: And these were great ideas that worked and still do.
Dantzig: Yes, I was very lucky.
Lustig: What would you say is the most invalid criticism of optimization?
Dantzig: Saying: "It's a waste of time to optimize because one does not really know what are the exact values of the input data for the program."
Lustig: Ok, let's turn this around. What would you say is the greatest potential of optimization?
Dantzig: It has the potential to change the world.
How George Dantzig Solved the Diet Problem
Lustig: What were the first problems that were solved by the simplex method by hand or on a computer?
Dantzig: I have a good description in my book "Linear Programming and Extensions". It says: "One of the first applications of the simplex algorithm was to the determination of an adequate diet that was of least cost. In the fall of 1947, Jack Laderman of the Mathematical Tables Project of the National Bureau of Standards undertook, as a test of the newly proposed simplex method, the first large-scale computation in this field. It was a system with nine equations in seventy-seven unknowns. Using hand-operated desk calculators, approximately 120 man-days were required to obtain a solution." "The particular problem solved was one which had been studied earlier by George Stigler (who later became a Nobel Laureate) who proposed a solution based on the substitution of certain foods by others which gave more nutrition per dollar. He then examined a "handful" of the possible 510 ways to combine the selected foods. He did not claim the solution to be the cheapest but gave his reasons for believing that the cost per annum could not be reduced by more than a few dollars. Indeed, it turned out that Stigler's solution (expressed in 1945 dollars) was only 24 cents higher than the true minimum per year $39.69."
Lustig: When you solved this problem, was pivoting done by hand?
Dantzig: Yes. All computations were done using hand calculators.
Lustig: I imagine there must have been a large team of people doing the arithmetic?
Dantzig: Yes. Perhaps a team of 10 people.
How Anne Dantzig Solved the Diet Problem
Dantzig: My Hungarian friend Andrew Vazsonyi wrote a sketch about how my wife upstaged me.
Lustig: I think I heard the story, but would you mind retelling it?
Dantzig: This is a cartoon drawn by my friend Andrew. If you look at this picture here it's pretty crude. You see vinegar, molasses, bran, and bouillon, meaning bouillon cubes, and you see here the simplex method and you see my wife's name Ann Dantzig spelled wrong. She spells it with an -e like the French do. The story is that I left the Pentagon in 1952 and took a position with the Rand Corporation. I decided to use the simplex method and linear programming to solve a diet problem designed for me to lose weight. Anne agreed she would prepare my meals according to what the computer declared was the optimal diet. So I called up my wife one day and said: "We've solved the diet problem for me, George Dantzig, and I want you to be ready when we run it, to cook supper and prepare it according to, by the whatever the computer says."
So it's getting late in the day and finally Anne calls me up and she says: "Well, what's for supper?" And I said: "Well, we ran the program. A couple of gallons of vinegar and some other stuff were the optimum diet. We'll just gonna have to take vinegar now as our food." Of course, we decided vinegar was not a food. The next day, we deleted vinegar from the list of foods eligible to be in the diet and it found an optimal diet containing, among other foods, 200 bouillon cubes.
Lustig: Cubes dissolved in a cup of hot water to make a cup of soup?
Dantzig: Yes. Anne said: "Well, I'll buy the very best bouillon cubes money can buy, but be prepared to go to the hospital. I decided to start with five per day and gradually work up to a couple hundred bouillon cubes per day. Have you ever tasted five bouillon cubes dissolved in a cup of hot water?
Lustig: No. What does it taste like?
Dantzig: It tastes like pure brine. I decided that two bouillon cubes was a proper upper limit per day. Each day we either eliminated or placed an upper bound on the amount of some other food in the diet.
Lustig: You solved a new optimization problem each day by hand!
Dantzig: Not by hand. We were solving them on a RAND computer.
Lustig: Ok. Was it a big effort solving a new optimization problem every day?
Dantzig: No. It was easy to drop a column from the tableau, or to place an upper bound on one of the variables.
Lustig: Right.
Dantzig: And by this time Anne got tired of the whole business because, see... I was calling her telling her what's for supper and she says: "No, I'll put you on a diet." So she put me on a diet and that was the end of the story. And then my friend, Andy Vazsonyi, he's Hungarian with a sense of humor, wrote a story about it. His story does not match my recollection...
Planning Under Uncertainty
Dantzig: Planning under uncertainty. This, I feel, is the real field that we should be all working in.
Lustig: Wasn't that always your interest from the very beginning? I think we've made good progress. But our ability to solve uncertainty problems is still in its infancy.
Dantzig: Correct. Those of us who were doing the planning right from the very beginning understood that the real problem was to be able to do planning under uncertainty. The mathematical models that we put together act like we have a precise knowledge about the various things that are happening and we don't. So we need to have plans that actually hedge against these various uncertainties.
Lustig: There's been a lot of progress, especially over the past ten years, within the research community on planning under uncertainty. What would you say are barriers stopping it from being more widely used in practice?
Dantzig: Lack of understanding by the planning community and the scientific community of how much better off the world and our country would be if planning under uncertainty models were more widely applied. One day we are paying low, low rates for electricity and the next thing you know it becomes short. My bill for utilities, which used to be around two or three hundred dollars, is now eight hundred dollars overnight. It just goes through the sky. A lot of things which they call globalization to me look very, very dangerous from the point of view of just protecting the country.