June 2003

The Simplex Solution

The mission to improve the widely used simplex-method algorithm showed instead why it works so well.

By Megan Vandre

While sitting in a courtroom, waiting to find out if he would be chosen for jury duty, Daniel Spielman had a revelation-all the work he and colleague Shanghua Teng had built up over the past three years was a house of cards. "I'll never forget," says Spielman, an associate professor of mathematics. "As I was sitting there waiting-fortunately not to get picked-I had this awful experience of realizing everything we'd been doing was wrong. I thought of throwing away my research program." And in that instant, the cards collapsed.

The pair had been trying to discover a way to improve the simplex method, one of the most widely used algorithms in the world. It enables many of the complex systems we take for granted-such as telecommunications networks and scheduling for fleets of delivery vehicles or airline flights-to work as efficiently and inexpensively as possible. As a new assistant professor, Spielman wanted to establish himself within the world of mathematics and gain tenure at MIT by working on a big challenge, namely, making the algorithm simpler, faster, and better. But after that day at the courthouse, when he realized that applying concepts from an unrelated area to the simplex algorithm was a dead end, he knew he would have to find another big breakthrough to achieve his goals.

A few days later, like a person whose home has been destroyed by a hurricane or tornado, Spielman began to salvage what was left of his ruin of research. And that was when the really big idea hit: though his work couldn't improve the simplex method, perhaps it could explain it. The method had been developed in 1947, but after more than 50 years of analysis, no one had been able to figure out why it worked. Spielman's hunch turned out to be right. After another three years of collaborative work and hundreds of mathematical formulae, he and Teng, a professor at Boston University, can now explain why the simplex method works. This may allow the so-called optimization experts to solve even more complex organizational problems. Already, the explanation, called "smoothed analysis," has been cited by the National Science Foundation as a major advance in information technology.