Research Reveals the Optimal Way to Optimize
The original version of this story appeared in Quanta Magazine.
In 1939, while arriving late for his statistics class at UC Berkeley, George Dantzig, a first-year graduate student, copied two problems from the board, thinking they were homework. He found the homework “more difficult to do than usual,” he later recounted, and apologized to the teacher for taking a few extra days to complete it. A few weeks later, his professor told him that he had solved two famous open statistics problems. Dantzig’s work would form the basis of his doctoral thesis and, decades later, the inspiration for the film. Goodwill Hunt.
Danzig received his doctorate in 1946, just after World War II, and he soon became a mathematics advisor to the new U.S. Air Force. As with all modern wars, the outcome of World War II depended on the careful allocation of limited resources. But unlike previous wars, this conflict was truly global in scope and was won largely through sheer industrial might. The United States could simply produce more tanks, aircraft carriers, and bombers than its enemies. Knowing this, the military became extremely interested in optimization problems—how to strategically allocate limited resources in situations that might involve hundreds or even thousands of variables.
The Air Force tasked Danzig with finding new ways to solve such optimization problems. In response, he invented the simplex method, an algorithm that drew on some of the mathematical techniques he had developed while solving his blackboard problems nearly a decade earlier.
Nearly 80 years later, the simplex method is still one of the most used tools when a logistics or supply chain decision must be made under complex constraints. It’s effective and it works. “He always ran fast, and no one saw that he wouldn’t,” said Sophie Huiberts of the National Center for Scientific Research (CNRS).
At the same time, there is a curious property that has long cast a shadow over Danzig’s method. In 1972, mathematicians proved that the time required to complete a task could increase exponentially with the number of constraints. So no matter how fast the method is in practice, theoretical analyzes have always come up with worst-case scenarios that imply it could take exponentially longer. For the simplex method, “our traditional tools for studying algorithms don’t work,” Huiberts said.
But in a new paper to be presented in December at the Foundations of Computer Science conference, Huiberts and Eleon Bach, a doctoral student at the Technical University of Munich, appear to have overcome this problem. They made the algorithm faster and also provided theoretical reasons why the long-feared exponential runtimes do not materialize in practice. The work, which builds on a landmark 2001 result by Daniel Spielman and Shang-Hua Teng, is “brilliant.” [and] magnificent,” according to Teng.
“This is a very impressive piece of technical work, which masterfully combines many of the ideas developed in previous lines of research, [while adding] really interesting new technical ideas,” said László Végh, a mathematician at the University of Bonn who was not involved in the effort.
Optimal geometry
The simplex method was designed to solve a class of problems like this: Suppose a furniture company makes cabinets, beds, and chairs. Coincidentally, each wardrobe is three times more profitable than each chair, while each bed is twice as profitable. If we wanted to write this as an expression, using A, bAnd c to represent the quantity of furniture produced, we would say that the total profit is proportional to 3A + 2b + c.
To maximize profits, how many of each item should the company produce? The answer depends on the constraints it faces. Let’s say the company can produce a maximum of 50 items per month, so A + b + c is less than or equal to 50. Cabinets are more difficult to make – no more than 20 can be produced – so A is less than or equal to 20. Chairs require special wood, and it is in limited supply, so c must be less than 24.
The simplex method turns situations like this, although often involving many more variables, into a geometry problem. Imagine graphing our constraints to A, b And c in three dimensions. If A is less than or equal to 20, we can imagine a plane on a three-dimensional graph perpendicular to the A axis, cutting it through A = 20. We would stipulate that our solution must lie somewhere on or below this plane. Likewise, we can create limits associated with the other constraints. Combined, these boundaries can divide space into a complex three-dimensional shape called a polyhedron.
