George Bernard Dantzig


Quick Info

Born
8 November 1914
Portland, Oregon, USA
Died
13 May 2005
Palo Alto, California, USA

Summary
George Dantzig was an American mathematical scientist who worked in operations research, computer science, economics and statistics. He is best known for inventing the simplex algorithm for linear programming.

Biography

George Dantzig's parents were Tobias Dantzig and Anja Ourisson. Tobias was born in Russia, but went to France where he studied mathematics in Paris being taught there by Poincaré. At this time Tobias met Anja who was at the Sorbonne at this time also studying mathematics. They married and emigrated to the United States, settling in Oregon. Tobias believed that his strong Russian accent would prevent him from obtaining jobs other than as a labourer, and at first his jobs included that of lumberjack, road builder and painter. It was into this very poor family that George was born.

Tobias and Anja chose names for their children hoping that these would influence their future careers. George was named "George Bernard" after George Bernard Shaw since his parents hoped their first child would become a writer. Similarly George's younger brother was named Henry after Henri Poincaré, and he did indeed become a mathematician. Tobias was fortunate to gain the chance of reading for a Ph.D. in mathematics at Indiana University, while Anja obtained a Master's degree in French becoming a linguist at the Library of Congress in Washington D.C.

The family were now living in Washington D.C., and there George attended Powell Junior High School where his progress in mathematics was, at first, rather poor. Encouraged by his father, and determined to do well in mathematics and science, he soon began to obtain top marks in mathematics. This continued at Central High School where he became fascinated by geometry. By this time he was getting strong support from three people: an outstanding mathematics teacher at the High School, a school friend who would go on to become a professor of mathematics at Berkeley, and his father. George later wrote that his father:-
... gave me thousands of geometry problems while I was still in high school. ... the mental exercise required to solve them was the great gift from my father. The solving of thousands of problems during my high school days - at the time when my brain was growing - did more than anything else to develop my analytic power.
Tobias was working on his most famous work Number: the language of science in the late 1920s and George helped him. He later wrote:-
As a teenager, I prepared some of the figures that appeared in the book.
The book was published in 1930 and when it was reprinted in the 1970s a reviewer wrote:-
Since its first appearance nearly half a century ago the book has gone through a number of printings and has deservedly maintained its popularity.
After graduating from High School, Dantzig decided to study mathematics at the University of Maryland, where by this time his father was on the Mathematics Faculty. Despite the improved status of his family, Dantzig's parents were still quite poor and not in a position to finance their son through a more prestigious university. He received his A.B. in Mathematics and Physics from the University of Maryland in 1936 and in the summer of that year he married Anne Shmuner. The newly married couple moved to Ann Arbour where Dantzig began graduate studies at the University of Michigan as a Horace Rackham Scholar. In 1937 Dantzig was awarded an M.A. in mathematics, having studied under T H Hildebrandt, R L Wilder and G Y Rainer.

Unhappy with abstract mathematics, the only courses he enjoyed being on statistics, Dantzig decided to give up his graduate studies. He moved to Washington where he worked as a Junior Statistician on a project "Urban study of consumer purchase" at the U.S. Bureau of Labor Statistics from 1937 to 1939. Having read statistics papers by Neyman, Dantzig wrote to him in 1939 asking if there was any possibility he could obtain a teaching assistantship at Berkeley so that he could complete his doctoral studies under Neyman's supervision. It took Neyman a little while to arrange the teaching assistantship but he managed to do so and Dantzig began for a second time to undertake graduate studies. We quote an often repeated story from this time in Dantzig's own words [3] (see also [2]):-
During my first year at Berkeley I arrived late one day to one of Neyman's classes. On the blackboard were two problems which I assumed had been assigned for homework. I copied them down. A few days later I apologized to Neyman for taking so long to do the homework - the problems seemed to be a little harder to do than usual. I asked him if he still wanted the work. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever.

About six weeks later, one Sunday morning about eight o'clock, Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." For a minute I had no idea what he was talking about. To make a long story short, the problems on the blackboard which I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them.
When the United States entered World War II in 1941 Dantzig put his graduate studies on hold for a second time, although by this time he had already completed the coursework and written his Ph.D. thesis. He went to Washington and joined the Air Force as a civilian. From 1941 to 1946 he was Head of the Combat Analysis Branch, U.S.A.F. Headquarters Statistical Control. In 1944 he was awarded the War Department Exceptional Civilian Service Medal. He wrote of his time there:-
My office collected data about sorties flown, bombs dropped, aircraft lost... I also helped other divisions of the Air Staff prepare plans called "programs". ... 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.
In 1946, after a break of five years, Dantzig returned to Berkeley for one semester, receiving his doctorate in mathematics from the University of California. He was offered an academic post by Berkeley but had turned down the offer:-
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.
By June 1946 he was in Washington considering a number of different possible jobs. His colleagues at the Pentagon asked him to take on the job of mechanizing the planning process. This appeared to fit in exactly with his interests so that year he was appointed Mathematical Advisor at the Defense Department to undertake the task.

In 1947 Dantzig made the contribution to mathematics for which he is most famous, the simplex method of optimisation. It grew out of his work with the U.S. Air Force where he become an expert on planning methods solved with desk calculators. In fact this was known as "programming", a military term that, at that time, referred to plans or schedules for training, logistical supply or deployment of men. Dantzig mechanised the planning process by introducing "programming in a linear structure", where "programming" has the military meaning explained above. The term "linear programming" was proposed by T J Koopmans during a visit Dantzig made to the RAND corporation in 1948 to discuss his ideas. Having discovered his algorithm, Dantzig made an early application to the problem of eating adequately at minimum cost. He describes this in his book Linear programming and extensions (1963):-
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.
In [11] Dantzig wrote (see also [9], [10] and [12]):-
Linear programming is viewed as a revolutionary development giving man the ability to state general objectives and to find, by means of the simplex method, optimal policy decisions for a broad class of practical decision problems of great complexity. In the real world, planning tends to be ad hoc because of the many special-interest groups with their multiple objectives.
But he also modestly wrote:-
The tremendous power of the simplex method is a constant surprise to me.
The importance of linear programming methods was described, in 1980, by Laszlo Lovasz who wrote:-
If one would take statistics about which mathematical problem is using up most of the computer time in the world, then ... the answer would probably be linear programming.
Also in 1980 Eugene Lawler wrote:-
[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.
Balinski [4] writes:-
Mathematical programming has been blessed by the involvement of at least two exceptionally creative geniuses: George Dantzig and Leonid Kantorovich.
He then goes on to say that Kantorovich received the Nobel Prize for his contribution and expresses "outrage" that Dantzig did not. Koopmans also had a share of this Nobel prize.

Dantzig became a research mathematician with the RAND Corporation in 1952 and during this period led the work on implementing linear programming on computers. Orchard-Hays writes in [14]:-
The systematic development of practical computing methods for linear programming began in 1952 at the Rand Corporation in Santa Monica, under the direction of George B Dantzig. The author worked intensively on this project there until late 1956, by which time great progress had been made on first-generation computers.
However, feeling that the RAND Corporation was not providing him with a source of fresh ideas, he took up an appointment as professor at Berkeley in 1960 and he was appointed Chairman of the Operations Research Center. While there he wrote Linear programming and extensions (1963). A reviewer wrote:-
An impressive book, the work is very complete, its scientific level high, and its reading pleasant.
In 1966 he was appointed Professor of Operations Research and Computer Science at Stanford University where he remained for the rest of his career.

His work in a wide range of topics related to optimisation and operations research over the years has been of major importance. However, writing in 1991, Dantzig noted that:-
... 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.
Dantzig has received many honours including the Von Neumann Theory Prize in Operational Research in 1975; The National Medal of Science presented by the president of the United States in 1976; the National Academy of Sciences Award in Applied Mathematics and Numerical Analysis in 1977; the Harvey Prize in Science and Technology from Technion, Israel, in 1985; the Silver Medal from the Operational Research Society of Britain in 1986; the Adolph Coors American Ingenuity Award Certificate of Recognition from the State of Virginia in 1989; and the Special Recognition Award from the Mathematical Programming Society in 1994.

The citation for the Medal of Science states that it was awarded:-
For inventing linear programming and discovering methods that led to wide-scale scientific and technical applications to important problems in logistics, scheduling, and network optimization, and to the use of computers in making efficient use of the mathematical theory.
The citation for The Harvey Prize reads:-
In recognition of his outstanding contribution to engineering and the sciences through his pioneering work in mathematical programming and his development of the simplex method. His work permits the solution of many previously intractable problems and has made linear programming into one of the most frequently used techniques of modern applied mathematics.
His work is summarised by Stanford University as follows:-
A member of the National Academy of Engineering, the National Academy of Science, the American Academy of Arts and Sciences and recipient of the National Medal of Science, plus eight honorary degrees, Professor Dantzig's seminal work has laid the foundation for much of the field of systems engineering and is widely used in network design and component design in computer, mechanical, and electrical engineering.


References (show)

  1. M Aigner, Diskrete Mathematik, in Ein Jahrhundert Mathematik 1890-1990 (Braunschweig, 1990), 83-112.
  2. D J Albers and C Reid, An interview with George B. Dantzig : the father of linear programming, College Math. J. 17 (4) (1986), 293-314.
  3. D J Albers, G L Alexanderson and C Reid, More mathematical people. Contemporary conversations (Boston, MA, 1990).
  4. M L Balinski, Mathematical programming : journal, society, recollections, in J K Lenstra, A H G Rinnooy, K Schrijver and A Schrijver (eds.), History of mathematical programming (Amsterdam, 1991), 5-18.
  5. G B Dantzig, A look back at the origins of linear programming (Chinese), Chinese J. Oper. Res. 3 (1) (1984), 71-78.
  6. G B Dantzig, Impact of linear programming on computer development, in Computers in mathematics, Stanford, CA, 1986 (New York, 1990), 233-240.
  7. G B Dantzig, Linear programming. The story about how it began: some legends, a little about its historical significance, and comments about where its many mathematical programming extensions may be headed, in J K Lenstra, A H G Rinnooy, K Schrijver and A Schrijver (eds.), History of mathematical programming (Amsterdam, 1991), 19-31.
  8. G B Dantzig, Origins of the simplex method, in S G Nash (ed.), A history of scientific computing (Reading, MA, 1990), 141-151.
  9. G B Dantzig, Reminiscences about the origins of linear programming, in Mathematical programming, Rio de Janeiro, 1981 (Amsterdam, 1984), 105-112.
  10. G B Dantzig, Reminiscences about the origins of linear programming, in A Schlissel (ed.), Essays in the history of mathematics, American Mathematical Society, San Francisco, Calif., January 1981 (Providence, R.I., 1984), 1-11.
  11. G B Dantzig, Reminiscences about the origins of linear programming, in Mathematical programming : the state of the art, Bonn, 1982 (New York, 1983), 78-86.
  12. G B Dantzig, Reminiscences about the origins of linear programming, Oper. Res. Lett. 1 (2) (1981/82), 43-48.
  13. G B Dantzig, Time-staged methods in linear programming : comments, early history, future prospects, in Large scale systems, Cleveland, Ohio, 1980 (Amsterdam-New York, 1982), 19-30.
  14. G B Dorfman, R The discovery of linear programming, Ann. Hist. Comput. 6 (3) (1984), 283-295.
  15. T H Kjeldsen, The emergence of nonlinear programming : interactions between practical mathematics and mathematics proper, Math. Intelligencer 22 (3) (2000), 50-54.
  16. W Orchard-Hays, History of mathematical programming systems, Ann. Hist. Comput. 6 (3) (1984), 296-312.
  17. Professor George Dantzig : Linear Programming Founder Turns 80, SIAM News (November 1994).
  18. Selected publications of George B Dantzig, in Mathematical programming I, Math. Programming Stud. No. 24 (1985), xi.

Additional Resources (show)


Honours (show)


Cross-references (show)


Written by J J O'Connor and E F Robertson
Last Update April 2003