In Memoriam
The Life and Timesof the Father of Linear Programming
George B. Dantzig (1914-2005) — operations research/management science pioneer, mathematician, professor, educator, consultant and author — was instrumental in establishing the O.R. profession and the foundations of mathematical programming and its applications.
By Saul I. Gass
Dr. George B. Dantzig, the "Father of Linear Programming" and a founding member of The Institute of Management Sciences, died May 13, 2005 in Stanford, Calif. His formal education was as a mathematician which reflected his early interest in the subject and the influence of his father, Tobias Dantzig, a mathematics professor who studied under Henri Poincaré. George's seminal work can be summed up succinctly as the recognition and definition of the broad class of practical problems that can be studied as linear programs and the development of the simplex algorithm for solving them. These developments came after the beginnings of the emerging field of operations research, as developed by British scientists during World War II. Early books and reports on operations research (O.R.) had little or nothing to say about linear programming. But, before long, George's work became a central and mainstay feature of O.R. methods and their application.
|
Tobias emigrated from Russia, studied in Paris where he met and married Anja, a mathematics student at the Sorbonne, and came to Oregon in 1910. He first held a variety of jobs — lumberjack, road builder, house painter — before he obtained a teaching position at Indiana University where he received his doctorate in mathematics in 1916. He taught at Johns Hopkins University and the University of Maryland where he was chair of the mathematics department. Tobias was a student of the classics and a wonderful expositor of mathematics. His 1930 book, "Number, The Language of Science," was praised by Einstein: "This is beyond doubt the most interesting book on the evolution of mathematics which has ever fallen into my hands."
In the book "More Mathematical People," George recounts his early struggle with ninth grade algebra and how he became a top student in mathematics and science. "Geometry really turned me on," he wrote. To keep George from bothering him, Tobias kept feeding George thousands of geometry problems that helped George develop his analytical power. George attended the University of Maryland, College Park, and received his A.B. degree in mathematics and physics in 1936. He married Anne Shmuner that summer and they moved to Ann Arbor, Mich., where George received his M.A. in mathematics in 1938.
Although he had only one graduate course in statistics, George qualified for the Civil Service as junior statistician and, in 1937, accepted a job at the U.S. Bureau of Labor Statistics in Washington, D.C. At that time he felt that statistics was "just a bag of tricks," but, on the job, he learned many practical applications and became familiar with the work of Jerzy Neyman at U.C. Berkeley, all of which caused him to change his view about statistics. George wrote to Neyman about pursuing a Ph.D. under his direction, and Neyman managed to get him a teaching assistantship. George and Anne moved to Berkeley in 1939. At that time, statistics was part of the Berkeley mathematics department, and although George only took two statistics courses, both from Neyman, his dissertation was in statistics. Here is where the legend begins.
Urban Legend
If you search the Web for "urban legend George Dantzig" you will probably find the first hit to be "Snopes.com, The Unsolvable Math Problem." That site recounts the story of how George, coming in late for class, mistakenly thought two problems written on the board by Neyman were homework problems. After a few days of struggling, George turned his answers in. About six weeks later, at 8 a.m. on a Sunday morning, he and Anne were awakened by someone banging on their front door. It was Neyman who said, "I have just written an introduction to one of your papers. Read it so I can send it out right away for publication."
George's answers to the homework problems were proofs of then two unproven theorems in statistics. The Web site gives all the details about how George's experiences ended up as a sermon for a Lutheran minister and the basis for the film, "Good Will Hunting." The solution to the second homework problem became part of a joint paper with Abraham Wald who proved it in 1950, unaware that George had solved it until it was called to his attention by a journal referee. Neyman had George submit his answers to the "homework" problems as his doctoral dissertation.
In June 1941, prior to defending his dissertation, George accepted a job in Washington, D.C., with the Army Air Force's Combat Analysis Branch of Statistical Control. This delayed him from receiving his doctorate in mathematics from Berkeley until 1946. Although offered a teaching position at Berkeley at that time, he decided to stay at the Pentagon where he became the mathematical advisor to the comptroller of the newly established Department of the Air Force. The deciding factor in George's job decision was that the Berkeley salary offer was "too little."
Although he considered the Pentagon a holding place until he found a decent paying academic position, George's choice started him down a life-changing research path that led him to linear programming. The outcomes of this decision have been momentous: setting O.R. onto a new and major course of research and applications, and, more importantly, enabling the world's enterprises and governments to become more effective and efficient.
Origins of Linear Programming
George was challenged by his Pentagon colleagues to figure out how the Air Force could mechanize its planning process; to speed up the computation of deployment of forces and equipment, training and logistical support — all this during the world of desk calculators and IBM accounting equipment. George's study of Air Force requirements led him to adapt and generalize the structure behind Wassily Leontief's inter-industry model. His insight enabled him to state mathematically — for the first time — a wide class of practical and important problems that fell into the newly defined linear-programming structure. This was accomplished by July 1947.
By the end of that summer, George had developed the simplex method for solving such problems. Also, in June of 1947, the Air Force established a major task force to work on the high-speed computation of its planning process, later named Project SCOOP (Scientific Computation of Optimal Programs), with George as chief mathematician. He stayed with Project SCOOP until June 1952, when he joined the RAND Corporation as a research mathematician.
|
Beyond Project SCOOP
While at RAND, working alone or with a stellar cast of co-authors, George furthered linear programming as an important applied and mathematically sound approach for analyzing a wide range of real-world decision problems. His RAND research included development and analysis of the decomposition principle, discrete variable applications, knapsack problem, network and shortest route procedures, traveling salesman problem, revised simplex method, stochastic programming and much more.
In 1960, he began his illustrious academic career as professor of engineering science and chairman of the Operations Research Center, University of California, Berkeley. He moved to Stanford University in 1966 as professor of operations research and computer science, and was appointed the C. A. Criley Endowed Chair in Transportation in 1973. He retired in 1985 as professor emeritus, but taught and maintained an active research agenda until the fall of 1997.
  |
|
| Through the years: George B. Dantzig led an extraordinary life, punctuated with many achievements, memories and milestones, including a 1984 gathering of former Ph.D. students from both his Berkeley and Stanford days (right). See some familiar faces? |
During his academic career, he showed how to exploit the linear-programming model's generality: the formulation and solution of management problems in most major industries; the resolution of strategic and tactical problems in defense; the evaluation of plans and operational solutions of national and world-wide energy and other resource limited problems; theoretical advances in mathematics, statistics, economics, game theory and computer science; and the adaptation of the linear-programming model to a more general set of mathematical-programming problems. George also served as a consultant to a number of major companies.
Much of George's important early work is captured in his classic text "Linear Programming and Extensions" (1963). Students and researchers will find much of value in it: an historical discussion of how the field first developed, the basic elements of linear programming, and the remarkable mathematical and applied extensions of the field. More recently, George and Mukund Thapa co-authored a two-volume comprehensive overview of the current status of the field. Other aspects and stories about George's career are recounted in two of his articles: "Reminiscences about the origins of linear programming" and "Linear programming." Here you can read how Tobias Dantizg made his one and only contribution to linear programming by naming the primal problem (here ignoring his begetting of George).
George authored or co-authored seven books and more than 150 papers. One book, "Compact City: A Plan for a Liveable Urban Environment," joint with Thomas L. Saaty, shows another view of George's wide-range of interests. The book is "a nontechnical, introductory study about the feasibility of building a city that makes more effective use of the vertical dimension and the time dimension (through around-the-clock use of facilities) than do present cities." It includes a section on "Operations Research and the Total-System Approach," but no linear programming!
George was a frequent visitor to the International Institute of Applied Systems Analysis (IIASA) headquartered in Laxenburg, Austria. IIASA is "a non-governmental research organization that conducts inter-disciplinary scientific studies on environmental, economic, technological and social issues in the context of human dimensions of global change." In 1973-74, George and Anne spent a sabbatical year at IIASA with George serving as IIASA's head of the methodology group. Two stories of his IIASA days illustrate his innate curiosity and interest in solving real-world problems.
A few days after he arrived at IIASA, George called Ruth Steiner, the administrator who took care of visitors, with the following request: "In front of my office is a truck that is very long. I cannot imagine that it is advantageous to have such a length. Could you please find out what is in the truck, where it came from, what route it took, and how it got around corners?" The answers came back: "furniture from Salzburg, over the autobahn, by backing up several times." Some time later, George's research assistant informed Ruth that the company could save 40 percent of its costs if they used four smaller trucks and suggested she inform the company, which she did. As she reported: "They thought I was out of my mind."
At IIASA, George drank his soup out of a beer mug. When Ruth asked him why, he wrote out a "long mathematical formula which proved that there was less heat wasted using a beer mug compared to a soup bowl."
The legacy of George goes way beyond his research and teaching. It includes his friendship, his mentoring, his unselfishness with his time and ideas, the more than 50 Ph.D. students he guided through Berkeley and Stanford, and another 165 (once-removed) doctoral descendants. But one important item is missing from his résumé — the Nobel Prize.
The Swedish Misconnection
In 1975, Tjalling C. Koopmans and Leonid V. Kantorovich received the Nobel Prize in economics for their contributions to the theory of optimum allocation of resources, that is, linear programming, or in economic terms, to its extension as linear activity analysis. Those of us familiar with the origins and development of linear programming and its impact on economic theory were amazed and disappointed that George was not included as an honoree since a Nobel Prize can be shared by up to three living recipients.
According to Michel L. Balinski, Koopmans was profoundly distressed that George had not shared in the prize. Koopmans gave a gift of $40,000 to IIASA, the amount equal to his share of what George would have received. All three principals had worked and met at various times at IIASA. In a conversation I had with Koopmans shortly after the award, he told of his displeasure with the Nobel selection and how he had earlier written to Kantorovich suggesting that they both refuse the prize, certainly a most difficult decision for both, but especially so for Kantorovich. His work in this area received little recognition in the Soviet Union when it was first developed.
As Kantorovich noted (in a posthumous publication, 1987): "In the spring of 1939 I gave some more reports at the Polytechnic Institute and the House of Scientists, but several times met with the objection that the work used mathematical methods, and in the West the mathematical school in economics was an anti-Marxist school and mathematics in economics was a means for apologists of capitalism."
George noted in "Linear Programming and Extensions" that "Kantorovich should be credited with being the first to recognize that certain important broad classes of production problems had well-defined mathematical structures which, he believed, were amenable to practical numerical evaluation and could be numerically solved." (The book, "Activity Analysis of Production and Allocation" — the proceedings of the Cowles Commission for Research in Economics 1949 conference, edited by Koopmans — was the first formal source of George's work. In 1951, Koopmans proposed the term linear programming to describe George's new mathematical model.)
Awards and Honors
George was a Fellow of the Econometric Society, Institute of Mathematical Statistics, Association for the Advancement of Science, American Academy of Arts and Sciences and the Institute for Operations Research and the Management Sciences. He was a Member of the National Academy of Sciences and the National Academy of Engineering. He was president of The Institute for Management Sciences in 1966, and a founder and chair (1973-74) of the Mathematical Programming Society.
|
George received nine doctorate honorary degrees, but perhaps the one he most cherished was from his University of Maryland alma mater in 1976, 40 years after his graduation. The citation read, in part: "Dantzig's linear programming was one of the principle forces leading to the emergence of the mathematical science of decision making as a new discipline called operations research or management science in the 1950s."
It is difficult for me to complete this tribute to George. I could go on and on. A most suitable way to close is by quoting the citation I wrote for George's IFORS' Hall of Fame nomination:
"For over 50 years, Dantzig's continuing innovations have been of the highest order. The scientific and economic impacts that have resulted from Dantzig's work are immeasurable. How does one measure the fact that all major (and most minor) industries directly or indirectly use linear programming to aid them in the allocation of their resources and decision-making; that all computer systems (mainframes and PCs) 'learn' how to solve linear-programming problems as soon as they are 'born'; that the simplex method is imbedded into all PC spreadsheet systems; that national economic planning for the third world and developing countries are being guided by linear-programming techniques; that strategic and tactical military planning, management of military personnel; and a wide variety of logistical (peacetime and combat) problems are solved using linear programming; that mathematical and computer science research such as combinatorics, numerical analysis and the solution of large-scale problems have been aided by linear programming; and that such diverse applications as cancer screening, airlines scheduling, agricultural development, transportation and delivery systems, scheduling of personnel and petroleum refinery operations have been influenced by the work of George Dantzig?
"The professional and academic fields of operations research, management science, industrial engineering, as well as the mathematical and computer sciences, rest heavily upon his lifetime of work."
A former president of the Operations Research Society of America, Saul I. Gass is professor emeritus at the Robert H. Smith School of Business, University of Maryland.
References
- Albers, D. J., and Reid, C., 1986, "An interview with George B. Dantzig: The father of linear programming," College Mathematics Journal, Vol. 17, No. 4, pp. 293-314.
- Albers, D. J., Alexanderson, G. L. and Reid, C. (eds.), 1990, "George B. Dantzig," pp. 61-79 in "More Mathematical People," Harcourt Brace Jovanovich, Boston.
- Balinksi, M. L., 1991, "Mathematical programming: Journal, society, recollections," pp. 5-18 in "History of Mathematical Programming," J. K. Lenstra, A. H. G. Rinnooy Kan, A. Schrijver, editors, North-Holland, Amsterdam.
- Dantzig, G. B., 1963, "Linear Programming and Extensions," Princeton University Press, Princeton.
- Dantzig, G.B., 1982, "Reminiscences about the origins of linear programming, Operations Research Letters, Vol. 1, No. 2, pp. 43-48.
- Dantzig, G.B., 2002, "Linear Programming," Operations Research, Vol. 50, No. 1, pp. 42-47.
- Dantzig, G. B., Saaty, T. L., 1973, "Compact City: A Plan for a Liveable Urban Environment," W. H. Freeman, San Francisco.
- Dantzig, G. B., Thapa, M. N., 1997, "Linear Programming: Introduction," Springer, New York.
- Dantzig, G. B., Thapa, M. N., 2004, "Linear Programming: Theory and Extensions," Springer, New York.
- Gass, S. I., 1989, "Comments on the history of linear programming," IEEE Annals of the History of Computing, Vol. 11, No. 2, pp. 147- 151.
- Gass, S. I., 2002, "The first linear-programming shoppe," Operations Research, Vol. 50, No 1, pp. 61-68.
- Kantorovich, L. V., 1987, "My journey into science (report to the Moscow Mathematical Society)," posthumous report of L. V. Kantorovich, prepared by V. L. Kantorovich, Russian Mathematics Surveys, Vol. 42, No. 2; also reprinted in "Functional Analysis, Optimization, and Mathematical Economics: A Collection of Papers Dedicated to the Memory of Leonid Vitalevich Kantorovich," L. J. Leifman, editor, Oxford University Press, New York, 1990.
- Koopmans, T, C., 1957, "Three Essays on The State of Economic Science," McGraw-Hill, New York.
- Mathematical Genealogy Project, 2005, www.genealogy.ams.org.
- Steiner, R., 1992, "Memories of IIASA, irreverent and reverent," IIASA Options, June 17.
|
OR/MS Today copyright © 2005 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.