The original version of this story appeared in Quanta Magazine. In 1939, George Dantzig, a first-year graduate student at UC Berkeley, arrived late to his statistics class and copied two problems off the blackboard, thinking they were for homework. He later recalled finding the homework "harder to do than usual" and apologized to the professor for taking extra time to finish it. A few weeks later, his professor informed him that he had solved two well-known open problems in statistics. This discovery would not only lay the groundwork for his doctoral dissertation but also inspire the film Good Will Hunting years later.
Dantzig earned his doctorate in 1946, right after World War II, and soon took on the role of mathematical adviser to the newly established US Air Force. Like all modern wars, the outcome of World War II hinged on efficiently managing scarce resources. However, unlike previous conflicts, this war was truly global and was primarily won through tremendous industrial capacity. The US was able to produce more tanks, aircraft carriers, and bombers than its adversaries. Recognizing this, the military became deeply interested in optimization problems, which involve the strategic distribution of limited resources amidst potentially hundreds or thousands of variables.
The Air Force assigned Dantzig to find new methods for solving such optimization challenges. From this task, he developed the simplex method, an algorithm that leveraged mathematical techniques he had been refining while tackling those initial blackboard problems nearly a decade earlier.
Fast forward almost 80 years, and the simplex method remains one of the most widely used tools for making logistical or supply-chain decisions under complex constraints. It’s efficient and consistently delivers results. "It has always run fast, and nobody’s seen it not be fast," noted Sophie Huiberts from the French National Center for Scientific Research (CNRS).
However, a curious issue has long overshadowed Dantzig’s method. In 1972, mathematicians proved that the time required to complete a task could increase exponentially with the number of constraints. Consequently, despite the practical speed of the simplex method, theoretical analyses have consistently suggested worst-case scenarios where it could take significantly longer to execute. "For the simplex method, our traditional tools for studying algorithms don’t work," said Huiberts.
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, seem to have tackled this challenge. They’ve not only made the algorithm faster but also provided theoretical insights explaining why the feared exponential runtimes do not typically occur in practice. Building on a pivotal 2001 result by Daniel Spielman and Shang-Hua Teng, Teng described their work as "brilliant [and] beautiful."
László Végh, a mathematician at the University of Bonn not involved in the research, commented, "It’s very impressive technical work, which masterfully combines many of the ideas developed in previous lines of research while adding some genuinely nice new technical ideas."
Optimal Geometry
The simplex method was designed to solve problems like the following: Imagine a furniture company that produces armoires, beds, and chairs. Interestingly, each armoire brings in three times the profit of each chair, while each bed doubles the profit of a chair. If we write this in mathematical terms, using a, b, and c to represent the quantities of each type of furniture made, the total profit can be expressed as 3a + 2b + c.
To maximize its profits, how many of each item should the company produce? The answer lies in the constraints it faces. For instance, suppose the company can make at most 50 items per month, meaning a + b + c must be 50 or fewer. Since armoires take more effort to produce, the company can make no more than 20, which gives a a maximum value of 20. Additionally, if chairs require a special type of wood that’s in limited supply, c must be less than 24.
The simplex method transforms these scenarios—often with even more variables—into a geometric problem. Picture graphing the constraints for a, b, and c in three dimensions. When a is less than or equal to 20, you can visualize a plane on a 3D graph that intersects the a-axis at a = 20. The solution must lie on or below that plane. Similar boundaries apply to the other constraints. Altogether, these boundaries create a complex three-dimensional shape known as a polyhedron.
