The original version of this story appeared in Quanta Magazine.

In 1939, upon arriving late to his statistics course at UC Berkeley, George Dantzig—a first-year graduate student—copied two problems off the blackboard, thinking they were a homework assignment. He found the homework “harder to do than usual,” he would later recount, and apologized to the professor for taking some extra days to complete it. A few weeks later, his professor told him that he had solved two famous open problems in statistics. Dantzig’s work would provide the basis for his doctoral dissertation and, decades later, inspiration for the film Good Will Hunting.

Dantzig received his doctorate in 1946, just after World War II, and he soon became a mathematical adviser to the newly formed US Air Force. As with all modern wars, World War II’s outcome depended on the prudent allocation of limited resources. But unlike previous wars, this conflict was truly global in scale, and it was won in large part through sheer industrial might. The US could simply produce more tanks, aircraft carriers, and bombers than its enemies. Knowing this, the military was intensely interested in optimization problems—that is, how to strategically allocate limited resources in situations that could involve hundreds or thousands of variables.

The Air Force tasked Dantzig with figuring out new ways to solve optimization problems such as these. 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 almost a decade before.

Nearly 80 years later, the simplex method is still among the most widely used tools when a logistical or supply-chain decision needs to be made under complex constraints. It’s efficient and it works. “It has always run fast, and nobody’s seen it not be fast,” said Sophie Huiberts of the French National Center for Scientific Research (CNRS).

At the same time, there’s a curious property that has long cast a shadow over Dantzig’s method. In 1972, mathematicians proved that the time it takes to complete a task could rise exponentially with the number of constraints. So, no matter how fast the method may be in practice, theoretical analyses have consistently offered 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.

Eleon Bach is a coauthor of the new result.

Photograph: Courtesy of Eleon Bach

But in a new paper that will 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 issue. They’ve made the algorithm faster, and also provided theoretical reasons why the exponential runtimes that have long been feared do not materialize in practice. The work, which builds on a landmark result from 2001 by Daniel Spielman and Shang-Hua Teng, is “brilliant [and] beautiful,” according to Teng.

“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,” said László Végh, a mathematician at the University of Bonn who was not involved in this effort.

Optimal Geometry

The simplex method was designed to address a class of problems like this: Suppose a furniture company makes armoires, beds, and chairs. Coincidentally, each armoire is three times as profitable as each chair, while each bed is twice as profitable. If we wanted to write this as an expression, using a, b, and c to represent the amount 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 make? The answer depends on the constraints it faces. Let’s say that the company can turn out, at most, 50 items per month, so a + b + c is less than or equal to 50. Armoires are harder to make—no more than 20 can be produced—so a is less than or equal to 20. Chairs require special wood, and it’s in limited supply, so c must be less than 24.

The simplex method turns situations like this—though often involving many more variables—into a geometry problem. Imagine graphing our constraints for 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 that is perpendicular to the a axis, cutting through it at a = 20. We would stipulate that our solution must lie somewhere on or below that plane. Likewise, we can create boundaries associated with the other constraints. Combined, these boundaries can divide space into a complex three-dimensional shape called a polyhedron.

Sophie Huiberts holds a geometric model of an optimization problem.

Photograph: Courtesy of Sophie Huiberts

The execution of the simplex algorithm from start to finish, represented geometrically, involves finding the path—from, say, the bottom vertex to the uppermost point—that involves the fewest steps or, equivalently, traces the fewest edges. The total number of steps, in turn, relates to the runtime (or “complexity”) of the algorithm, with the goal being to solve the problem in the minimum number of steps. Identifying the shortest route from bottom to top in this picture amounts to figuring out the most efficient form that such an algorithm can take.

Finding a quick and direct path might be easy, were it not for two things: First, the original shape is likely to be far more complicated than our example, with many more faces, vertices and edges. And second, there is no map to guide you. You can’t see the entire object you’re trying to navigate. Instead, you start at one vertex and make a choice regarding which edge to follow first. You do the same at the next vertex, and so on, not knowing for sure where the edge you chose will take you.

If you are extraordinarily unlucky, you could take the wrong turn at each vertex and get stuck in a labyrinth. “You could walk the longest possible path to get from A to B,” Bach said, “because at each corner there’s someone who tells you that you should go in the wrong direction.” That’s the kind of situation that could lead to the worst-case scenarios that take an exponential amount of time to complete.

In 2001, Spielman and Teng proved that the tiniest bit of randomness can help prevent such an outcome. Going back to the previous example—at the risk of greatly oversimplifying Spielman and Teng’s argument—let’s suppose that there are six choices at every corner you come to. If you’re always told the worst direction to go in, you’ll be in trouble. However, if you instead rely on a roll of the dice, you’ll have a five-out-of-six chance of avoiding the worst pick, and disaster may be averted. Injecting an element of randomness and uncertainty into the process is reasonable, given that in the real world, measurements are never exact. Spielman and Teng introduced randomness in an entirely different way, but they showed that the running time can never be worse than the number of constraints raised to a fixed power—for instance, n2—which is an example of what’s called polynomial time. That’s a lot better than exponential time, which takes the form of, say, 2*n*.

Shang-Hua Teng.

Photograph: Emilio Flores for Quanta Magazine

Daniel Spielman.

Photograph: Brandon Schulman

Nevertheless, this didn’t completely solve the issue. Their polynomial time values were still rather high, Huiberts noted—they included a term raised to the power of 30, which is a pretty big number for an exponent. So, over the past two decades, researchers have been making incremental progress in bringing this value down.

In their new paper, Bach and Huiberts relied on even more randomness in their algorithm to show that runtimes are guaranteed to be significantly lower than what had previously been established. They also showed that an algorithm based on the approach established by Spielman and Teng cannot go any faster than the value they obtained. It tells us, Huiberts said, “that we fully understand [this] model of the simplex method.”

“This marks a major advance in our understanding of the [simplex] algorithm,” said Heiko Röglin, a computer scientist at the University of Bonn, “offering the first really convincing explanation for the method’s practical efficiency.”

Nevertheless, Huiberts does not see this as the end of the line. The approach that started in 2001 with Spielman and Teng showed how runtimes can be reduced from exponential to polynomial time. The next logical step is to invent a way to scale linearly with the number of constraints. “That is the North Star for all this research,” she said. But it would require a completely new strategy. “We are not at risk of achieving this anytime soon.”

While the efforts of Bach and Huiberts are of theoretical interest to colleagues in their field, the work has not yielded any immediate practical applications. Nevertheless, it may serve to calm some of the worries that people might have about relying on software available today that is based on the simplex method. “While practical experiments show that these problems are always solved in polynomial time,” said Julian Hall, a lecturer in mathematics at the University of Edinburgh who designs linear programming software, Bach and Huiberts have provided stronger mathematical support for that intuition. “Hence it’s now easier to convince those who fear exponential complexity.”

---

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.