A mathematician’s son
George Bernard Dantzig was born on November 8, 1914, in Portland, Oregon, to Jewish parents, and was named after the Irish playwright George Bernard Shaw. His father, Tobias Dantzig, was a mathematician and linguist from the Russian Empire who had studied under the great French mathematician Henri Poincaré in Paris; George’s younger brother was named Henry Poincaré Dantzig in the master’s honour. His mother, Anja Ourisson Dantzig, was a Russian-born linguist whom Tobias had met at the University of Paris.
In the early 1920s the family moved to Washington, D.C., where his mother worked as a linguist at the Library of Congress and his father taught mathematics at the University of Maryland. Tobias Dantzig later wrote Number: The Language of Science, a celebrated popular history of mathematics. At home he challenged his son with hard problems, especially in projective geometry.
The homework that was not homework
Dantzig took a degree in mathematics and physics at the University of Maryland in 1936 and a master’s in mathematics at the University of Michigan in 1937, then worked as a junior statistician at the U.S. Bureau of Labor Statistics. In 1939 he began doctoral studies in statistics at the University of California, Berkeley, under Jerzy Neyman.
That year produced one of the most famous stories in mathematics. Arriving late to one of Neyman’s classes, Dantzig copied two problems from the blackboard, assuming they were homework. He found them a little harder than usual, solved them, and handed them in, thinking they were overdue. About six weeks later Neyman told him that the problems had been two famous unsolved questions in statistics. Neyman later told him to put the solutions in a binder, and he would accept them as a thesis. The story became an urban legend and inspired the opening of the 1997 film Good Will Hunting.
Planning a war
When the United States entered the Second World War, Dantzig left Berkeley to work as a civilian for the U.S. Army Air Forces. From 1941 to 1946 he headed the combat analysis branch of its Headquarters Statistical Control, helping to plan and track the enormous flows of aircraft, crews, parts and supplies that the air war required. The War Department decorated him for exceptional service in 1944.
He returned to Berkeley to finish his doctorate in 1946 but turned down a faculty post there to go back to the Air Force as mathematical adviser to the comptroller. His task was to mechanise the planning process: to find a way of deciding, among an astronomical number of possible plans, which was the best.
The word programming in linear programming came from this world. In the military of the 1940s, a programme was a schedule or plan of activities, and the Air Force’s planning effort was known as Project SCOOP. Dantzig’s task was to find a mathematical way to produce the best programme, and the name stuck long before computer programming gave the word its modern meaning.
The simplex method
In 1947 Dantzig formulated the general problem now called linear programming. Many real decisions share a common structure: there are limited resources, such as money, machines, workers or fuel; many activities that use them in fixed proportions; and a goal, such as lowest cost or highest output. Writing these relationships as linear equations and inequalities turns a planning question into a precise mathematical problem.
He then invented a way to solve it, the simplex method. The possible plans form a many-sided geometric shape, and the best plan lies at one of its corners. Instead of checking every corner, which for real problems would take longer than the age of the universe, the simplex method moves from corner to corner, always improving, until it can improve no further. Dantzig liked to illustrate the power of the idea with the problem of assigning 70 people to 70 jobs: there are more possible assignments than particles in the observable universe, yet the simplex method finds the best one quickly.
Linear programming had been anticipated in part by the Soviet mathematician Leonid Kantorovich, and John von Neumann contributed the theory of duality after Dantzig showed him the problem, but it was Dantzig’s formulation and his simplex method that made it a practical tool. Arriving at the same moment as the electronic computer, it spread rapidly into industry.
Some honours passed him by. In 1975 the Nobel Memorial Prize in Economic Sciences went to Kantorovich and Tjalling Koopmans for their contributions to the theory of optimum allocation of resources, a field built largely on linear programming, and many colleagues felt that Dantzig, whose method made the theory usable, deserved a share.
How the world runs on linear programming
Linear programming became one of the most widely used mathematical techniques ever devised. Oil refineries use it to decide how to blend crude oil into fuels; airlines use it to schedule fleets and crews; shipping and delivery companies use it to route goods; utilities use it to plan power generation; factories use it to plan production; farmers and food companies use it to formulate feed and diets at the lowest cost while meeting nutritional needs. The New York Times noted its use in utilities, refineries, investments, steel making, nutrition and commercial air routes.
When Dantzig died, his Stanford colleague Arthur Veinott said that experts estimated that between 10 and 25 percent of all scientific computation was devoted to the simplex method. It has been named one of the most important algorithms of the twentieth century. Each time a supermarket shelf is stocked from a distant warehouse at low cost, or an airline fits thousands of flights and crews together, Dantzig’s method or one of its descendants is likely at work.
The method has also been refined and challenged over the years. In theory, mathematicians found contrived examples on which the simplex method takes a very long time, and in 1984 Narendra Karmarkar introduced interior-point methods that can solve some huge problems faster. Yet in practice the simplex method has remained astonishingly efficient on real-world problems, and modern optimisation software still relies on it alongside the newer techniques.
RAND, Berkeley and Stanford
In 1952 Dantzig joined the mathematics division of the RAND Corporation, where he extended linear programming in many directions. With Philip Wolfe he developed the Dantzig–Wolfe decomposition for breaking very large problems into manageable pieces, and with Ray Fulkerson and Selmer Johnson he solved a 49-city travelling salesman problem, a landmark in the field of combinatorial optimisation. He also pioneered stochastic programming, for decisions made under uncertainty. His book Linear Programming and Extensions, published by Princeton University Press in 1963, became the standard text.
In 1960 he became professor at Berkeley and chairman of its Operations Research Center. In 1966 he moved to Stanford University as professor of operations research and computer science, where he founded the Systems Optimization Laboratory in 1973 and later held the C. A. Criley chair in transportation sciences. He also led the methodology group at the International Institute for Applied Systems Analysis in Austria, and he supervised generations of doctoral students.
Jewish roots and family life
Dantzig was the son of Jewish parents from the Russian Empire who had met in Paris and emigrated to the United States, part of the generation of Jewish intellectuals who brought European learning to American universities. His father’s love of mathematics, and his parents’ devotion to scholarship, shaped his whole life. Sources do not describe him as religiously observant.
In 1936 he married Anne S. Shmuner; they were married for 68 years and had three children, David, Paul and Jessica. Colleagues remembered him as modest, generous with ideas and devoted to his students.
Honours and last years
Dantzig was a member of the National Academy of Sciences, the National Academy of Engineering and the American Academy of Arts and Sciences. He received the first John von Neumann Theory Prize in operations research in the mid-1970s, and on October 18, 1976, President Gerald Ford presented him with the National Medal of Science for inventing linear programming and methods with wide applications. He received honorary doctorates from institutions including the Technion in Israel, the University of Maryland and Yale, and the Mathematical Programming Society created the George B. Dantzig Prize in his honour.
He continued to write well into his eighties, publishing two volumes of Linear Programming with Mukund Thapa in 1997 and 2003. He died at his home in Stanford, California, on May 13, 2005, aged 90, of complications from diabetes and cardiovascular disease.
Legacy
George Dantzig gave the world a way to make the best use of limited resources, and few inventions have saved as much waste, money and effort. His simplex method runs inside the planning systems of airlines, factories, refineries, power companies and food suppliers on every continent, quietly cutting costs that would otherwise be passed on to consumers and reducing wasted fuel and materials.
Today linear programming is taught to engineering, business and economics students around the world, and the George B. Dantzig Prize recognises major contributions to mathematical optimisation every three years.
His former student Robert Freund described his work as yielding bold new mathematical tools. The student who mistook unsolved problems for homework went on to solve a far larger one: how to choose the best plan among more possibilities than anyone could ever count.
Sources & further reading
George Dantzig, Wikipedia · George B. Dantzig obituary, The New York Times (MacTutor archive) · George Bernard Dantzig, IEEE Computer Society history · Jewish Computer and Information Scientists, jinfo.org · Researched from the sources above and checked against them. Spotted an error? Tell us.
A life of tikkun olam. This is part of tikkun olam, the Jewish idea of repairing the world, and every one of us can add to it.