If there is a Godfather of it all - the entire field of large-scale optimization - it is George Dantzig, the Stanford professor emeritus of operations research and computer science who developed the simplex method on which Yossi Sheffi has built his work. Run a Google search on Dantzig and you'll find yourself inundated with online tributes to the man whose early work has inspired the field of linear programming for which simplex is the preeminent tool. The versatility and economic impact of linear programming in today's industrial world is truly awesome. It is deployed to solve any problem involving limited resources, an overall objective, and a choice of actions to be taken - everything from work schedules to production plans.
Dantzig lives on the Stanford campus in Palo Alto, California. When I visit him, the 87-year-old professor, wearing purple pajamas, takes me into the living room of his 1960s ranch-style home, and the first thing he wants to set straight is a matter of semantics. He didn't "retire" from Stanford. He "was retired," clearly against his wishes, just before he turned 83. Drawn shades block out the oppressively bright sunlight. I ask him about simplex. He points to a multisided black glass sculpture on his marble coffee table, a gift from a group of students at the University of Illinois. It's an artistic interpretation of his work.
"Simplex doesn't refer to being simple," he says. "It refers to a geometric mathematical object. A triangle is an example of a simplex - a triangle with everything on the inside. It's the corners, the edges, the interior. Simplex is the movement in space, higher-dimensional space, from one of these simplex objects to another."
During World War II, Dantzig served as chief of the combat analysis branch for the US Air Force, in charge of tracking the numbers of sorties flown and bombs dropped. After the war, he turned down a low-paying job at UC Berkeley in favor of continuing to work for the Air Force. "We were trying to mathematize planning," he explains, "which up until then was an empirical process." The first step was to establish a single goal - like maximizing the allocation of aircraft - which was radical. "And you couldn't reach it anyway," says Dantzig. "The algorithm wasn't there."
Dantzig's quest for an algorithm led him to Tjalling Koopmans, the University of Chicago economist who later won a Nobel Prize, and John von Neumann, then the leading mathematician in the world. Koopmans recommended a mathematician named Leon Hurwitz, and with Hurwitz's help, Dantzig invented the algorithm that became the simplex method. Its first application was in Air Force logistics.
Professor Dantzig again points to the sculpture. "Imagine you're sitting on one of the corners. You look down the different edges. Simplex measures the next corner, how good it's going to be based on the value of the objective. It looks at every one of those neighboring corners and gives you a measure of goodness. Then it looks down that edge versus that edge versus that edge. The one that gets the highest score, you go down that one."
He sits back for a silent moment, taking in the sculpture, then asks: "Would you like some coffee?" As he makes his way to the kitchen, his invention busily upgrades countless Wall Street investment portfolios, determines millions of urgent manufacturing schedules, and dispatches thousands of trucks across hundreds of dizzying networks.
