George Bernard Dantzig: The Pioneer of Linear Optimization

John R. Birge
University of Chicago Booth School of Business

George Dantzig introduced the world to the power of optimization, creating trillions of dollars of value and saving countless years of life across the globe. In this laudation, John Birge describes the fascinating life and incredible accomplishments of a scholar whose footprints led the way to almost everything the global economy produces.

George Bernard Dantzig (1914-2005) introduced the world to linear programming and, more generally, to the power of optimization. His work created trillions of dollars of value and preserved countless years of life across the globe. By creating the simplex method for solving linear programs he made vastly complex decisions amenable to computation. By demonstrating the duality between activities and prices he paved the way for new analyses resulting in greater market efficiency. His work has supported growing economies and improved healthcare, saving many from hunger and extending lives around the world. Dantzig’s optimism and determination inspired many to increase their own achievements.

Dantzig became interested in mathematics as a child, although his parents, Tobias and Anja, had named him after George Bernard Shaw in the hope that he would become a writer. His father, a mathematics professor at the University of Maryland, gave George “thousands of geometry problems” that fascinated him and honed his powers of analysis. After earning an undergraduate degree in mathematics and physics at Maryland, Dantzig went on to pursue graduate studies in mathematics at the University of Michigan. Finding the program’s focus on abstract mathematics uninspiring, he left Ann Arbor and returned to Washington to work at the Bureau of Labor Statistics (BLS). His new profession prompted him to begin working on practical applications of mathematics. As he often remarked later in life, his many mathematical discoveries, while sometimes stated abstractly, were all inspired by practical problems facing firms, organizations, or governments.1

After a few years at BLS, Dantzig found new inspiration for research in the work of Jerzy Neyman at the University of California, Berkeley. The real tale of Dantzig’s world-changing career and professional fame began with the now-legendary moment when he arrived late to Neyman’s class. In previous weeks, Neyman had customarily written the week’s homework problems on the board at the beginning of the period. So when Dantzig saw two problems on the board, he wrote them down to work on and hand in before the next class session. He found the problems a bit more difficult than usual and was a few days late in completing them. He took his solutions to Neyman’s office to ask the professor if he still wanted to review the homework. Neyman told him to leave them on his desk, which was so covered with papers that Dantzig feared his hard work would be lost forever.

Dantzig heard nothing from Neyman for several weeks, but then he was awakened early on a Sunday morning by the sound of vigorous knocking on his downstairs door. When he answered, Neyman abruptly informed him that his dissertation was done. The two problems Dantzig had solved for homework were actually two famous unsolved (and until then, unsolvable) problems in statistics. Dantzig’s unshakeable belief that he could solve the problems has become a symbol of the power of positive thinking. His story continues to inspire others to undertake difficult tasks.

As well as offering a stunning example of individual achievement, Dantzig’s solutions of the ‘homework’ problems laid the groundwork for the beginning of linear programming and countless subsequent applications. While working for the U.S. Air Force during and after World War II, Dantzig began to see ways to improve its efficiency. He sought to automate the planning or programming process of delineating detailed requirements for producing, assembling, training, and locating all of the military’s personnel and equipment. He developed a model for finding the best combination and levels of activities and uses of resources which became known as linear programming. Its solutions were provided by the pioneering algorithm inspired by his dissertation: the simplex method. Fortuitously, his development of this numerical procedure coincided with the advent of computers and contributed to their development as well.2

Linear programs and Dantzig’s many other contributions to optimization have driven enormous increases in productivity throughout the global economy.

Linear programs and Dantzig’s many other contributions to optimization have driven enormous increases in productivity throughout the global economy. Industries with expensive capacity or limited production flexibility, like airlines, hotels, rental cars, and many retailers, have used revenue management models, often built on linear programming, to achieve revenue increases of 5 percent or more. The electric power industry also uses advanced optimization methods to reap cost savings that exceed 5 percent of their overall energy. The logistics field has also benefited enormously from optimization, reducing shipping costs by up to 50 percent in many industries including retail, chemical, tech, and consumer goods. In addition, much of modern finance and asset management is built on Markowitz’s efficient portfolio model, which was rooted in Dantzig’s work.3 Combining these accomplishments with uses in telecommunications, manufacturing, and more, and particularly in complex process industries like chemical manufacturing, linear optimization probably contributes over 5 percent to the overall output, or about $1 trillion each year, in the US alone.

Linear programming has become a vital tool in advancing artificial intelligence and machine learning, and it is used in electrical stimulation therapy, chemotherapy plans, drug discovery, radiation therapy designs, and finding optimal diets.

Beyond traditional industrial uses, linear programming has become a vital tool in advancing artificial intelligence and machine learning. Such optimization procedures have not just reduced costs and increased outputs across the globe, they have also saved countless lives. Linear programming is used in the phylogenetic analysis that determines the origins of organisms (including viruses, such as SARS-CoV-2, better known as the novel coronavirus). It is also used in electrical stimulation therapy, chemotherapy plans, drug discovery, radiation therapy designs, and finding optimal diets, an application which has drawn interest for more than seventy-five years.4

Linear programming and its various extensions continue to play an influential role in the economy and in all our lives.

Linear programming and its various extensions continue to play an influential role in the economy and in all our lives. The simplex method is also a remarkable tool, named one of the top ten algorithms of the twentieth century and an indispensable part of optimization to this day. Dantzig’s other contributions constitute the foundation upon which the development of many other decision-making tools over the past seventy years was built. Nonetheless, as Dantzig himself was known to point out, his most fundamental contribution may have been the very concept of an objective function.5 As he wrote, earlier planners and managers may have shied away from the notion of optimizing an objective because they thought it inconceivable to find an optimal solution among possibilities more numerous than the atoms in the universe. Dantzig dared to conceive of surmounting that imposing obstacle and succeeded, to the substantial benefit of us all.

Booth's John Birge, September 6, 2016. (Photo by Jean Lachat)

John Birge is the Hobart W. Williams Distinguished Service Professor of Operations Management at the University of Chicago Booth School of Business. His work follows that of his doctoral advisor, George Dantzig, in exploring ways to make better decisions.

Endnotes

  1. Much of this history appears in Dantzig’s interview in D.J. Albers and C. Reid, “An Interview with George B. Dantzig: The Father of Linear Programming,” The College Mathematics Journal, 17 (4) (Sep., 1986), pp. 293-314.
  2. Dantzig’s account of the simplex method’s role in the development of digital computers appears in G.B. Dantzig, “Impact of linear programming on computer development,” Technical Report SOL 85-07, Stanford University, 1985, https://apps.dtic.mil/dtic/tr/fulltext/u2/a157659.pdf.
  3. Markowitz’s discussion of Dantzig’s influence on his work appears at: http://hmarkowitz.com/about-harry-markowitz/.
  4. Dantzig’s discussion of the early history of this problem is in: G.B. Dantzig, “The diet problem,” Interfaces 20 (4) (1990), pp. 43-47.
  5. Dantzig’s description is in: G.B. Dantzig, “Linear programming,” Operations Research 50 (1) (2002), pp. 42—47.