In 1939, arriving late to his statistics course at UC Berkeley, first-year graduate student George Dantzig copied two problems off the blackboard, thinking they were a homework assignment. He found the homework “more difficult than usual”, later repeated it, and apologized to the professor for taking a few 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, provide inspiration for the film good will Hunting,
Dantzig received his doctorate in 1946, just after World War II, and he soon became a mathematical advisor to the newly formed US Air Force. Like all modern wars, the outcome of World War II depended on the judicious allocation of limited resources. But unlike previous wars, this conflict was truly global in scale, and it was won largely through industrial power alone. America can produce more tanks, aircraft carriers and bombers than its enemies. Knowing this, the Army was deeply interested in optimization problems—that is, how to strategically allocate limited resources in situations that might involve hundreds or thousands of variables.
The Air Force tasked Dantzig with finding new ways to solve such optimization problems. In response, he invented the simplex method, an algorithm based on some of the mathematical techniques he developed while solving his blackboard problems about a decade earlier.
Nearly 80 years later, when a logistics or supply-chain decision needs to be made under complex constraints, the simplex method is still one of the most widely used tools. It’s efficient and it works. “It has always run fast, and no one has ever seen it faster,” said Sophie Huberts of the French National Center for Scientific Research (CNRS).
At the same time, there is one unique property that has long cast a shadow over Dantzig’s method. In 1972, mathematicians proved that the time taken to complete a task could increase exponentially with the number of obstacles. Therefore, no matter how fast the method is in practice, theoretical analyzes have consistently offered a worst-case scenario, meaning it can take exponentially longer. For the simplex method, “our traditional tools for studying algorithms do not work,” Huberts said.
But in a new paper to be presented at the Foundations of Computer Science conference in December, Huberts and doctoral student Alon Bach of the Technical University of Munich look to overcome this issue. They have made algorithms faster, and also provided theoretical reasons why the long-feared exponential runtimes do not materialize in practice. This work, which is based on a landmark 2001 work by Daniel Spielman and Shang-Hua Teng, is “brilliant”. [and] Beautiful,’ according to Teng.
“This is very impressive technical work, which skillfully combines many of the ideas developed in previous lines of research, [while adding] Some really cool new technical ideas,” said mathematician Laszlo Wegh of the University of Bonn, who was not involved in the effort.
optimal geometry
The simplex method was designed to address a class of problems like this: Suppose a furniture company makes wardrobes, beds, and chairs. Incidentally, each wardrobe is three times more profitable than each chair, while each bed is twice as profitable. If we want to write it as an expression, use A, bAnd C To represent the quantity of furniture produced, we will say that total profit is proportional to 3A +2b , C,
To maximize profits, what amount of profit should the company make from each item? The answer depends on the obstacles he faces. Suppose the company can produce a maximum of 50 items per month A , b , C Is less than or equal to 50. Arsenal are hard to build – no more than 20 can be produced – so A Is less than or equal to 20. Chairs require special wood, and its supply is limited, so C Must be less than 24.
The simplex method transforms such situations – although often involving many more variables – into a geometry problem. Imagine graphing our odds A, b And C In three dimensions. If A is less than or equal to 20, then we can imagine a plane on a three-dimensional graph that is perpendicular to A axis, cutting through it A = 20. We will bet that our solution should be somewhere at or below that plane. Similarly, we can create boundaries associated with other constraints. Combined, these boundaries can divide space into a complex three-dimensional shape called a polyhedron.
<a href