Engines of Our Ingenuity

No. 2327:
GEORGE DANTZIG

by Andrew Boyd

Today, a Nobel Prize lost. The University of Houston's College of Engineering presents this series about the machines that make our civilization run, and the people whose ingenuity created them.

George Dantzig George B. Dantzig was born in 1914, named after Irish playwright George Bernard Shaw. His Russian father, Tobias, briefly studied with French mathematician Henri Poincaré before emigrating to the U.S. When his son showed proclivity in geometry, Tobias fed the boy's interest with geometry problems. Dantzig would later comment that "the mental exercise required to solve them was the great gift from my father."

In 1939, Dantzig began his doctorate in statistics at Berkeley. But, with WW-II underway, he soon put his studies on hold and went to work as Head of the Combat Analysis Branch at the Air Force Headquarters for Statistical Control. The armed forces had to get trucks, planes, people, food -- you name it -- into the field. The detailed plans for doing so were called "programs." These programs would serve as the foundation of Dantzig's legacy.

Just as there are many ways to get from New York to Los Angeles, there are many programs that will solve a military planning problem. Some are better than others. We need to know the possible solutions; then we need to know how to find the best one. It isn't easy. There are usually more solutions than we could ever evaluate one by one in the next billion years.

Simplex illustration Dantzig quickly recognized that problems like of the kind the military faced could be cast as problems in geometry. The possible solutions correspond to the points inside a diamond-like shape. Finding the best solution is like finding a specific corner on the diamond's surface. Dantzig came up with a computer algorithm for just that. It doesn't check all corners. It keeps finding better ones until it reaches the best. The process is remarkably fast, and can be used to solve previously impossible problems.

Dantzig's efforts gave birth to one of the most important mathematical tools ever used for solving complex decision problems. That tool is linear programming. The word "programming" does not refer to computer programs. It refers to those old military problems. His algorithm is called the simplex method.

Dantzig is known throughout the world as the father of linear programming. He received countless honors and awards in his life, including the National Medal of Science. But he was passed over by the Nobel Prize committee, even though linear programming was not. That decision shocked and dismayed many. Tjalling Koopmans was deeply distressed. He shared the 1975 Nobel Prize with Leonid Kantorovich for their contributions to linear programming. Koopmans even approached Kantorovich about refusing the prize. Nothing came of it, but he did donate what would've been Dantzig's share of the prize money to the institute where they'd once worked together.

We can only speculate about the decision of the prize committee, but there's an important distinction between Dantzig's work and the work of Koopmans and Kantorovich. The two prize winners emphasized economic theory. Dantzig emphasized the mathematical engineering needed to solve linear programs. There's no Nobel Prize in engineering or mathematics. Maybe there should be.

I'm Andy Boyd, at the University of Houston, where we're interested in the way inventive minds work.

(Theme music)


Gass, S.I. The Life and Times of the Father of Linear Programming. OR/MS Today, August 2005. Retrieved January 31, 2008. Dantzig illustration above is courtesy of this site.

George Dantzig. Retrieved January 31, 2008.

Press release for the 1975 Nobel Prize in Economics. Retrieved January 31, 2008.

Simplex algorithm. Retrieved January 31, 2008, from Wikipedia.



The Engines of Our Ingenuity is Copyright © 1988-2008 by John H. Lienhard.