Unlocking the mysteries of the Simplex-algorithm

The most popular optimization method is an algorithm, developed in 1947. Why is it still so successful? CWI researchers were able to shed some light on the matter.

Publication date
5 Mar 2024

Despite decades of explosive growth in computing power, despite far more and deeper mathematical and computer science knowledge, despite far more scientists working in the field of algorithms, it is still a 1947 algorithm that is the most successful for optimizing logistical problems. It is widely applied in areas ranging from manufacturing and transport to telecommunication. And the mystery is that no one can put their finger on theoretical reasons why this algorithm is so successful in practice. But over the past few years, CWI researchers have been able to shed some light on the matter, building on earlier work of American mathematicians.

Simplex method

The algorithm in question is the Simplex algorithm, devised by American George Dantzig (1914-2005), considered one of the founding fathers of linear programming. About the success of the Simplex method Dantzig said in 1982: “The tremendous power of the simplex method is a constant surprise to me.”

CWI researcher Daniel Dadush, leader of the Networks & Optimization group, realized that trying to shed some light on the mysteries of the Simplex algorithm was high risk, high gain research. But together with Sophie Huiberts, who worked first as a master student and later as a PhD student, he decided to take the risk, in the spirit of CWI’s long term mission.

Daniel Dadush. Picture: UU (Harold van de Kamp)
Daniel Dadush. Picture: UU (Harold van de Kamp)

Dadush: “To go beyond worst-case analysis, computer scientists Daniel Spielman and Shang-Hua Teng developed a model called smoothed analysis, in which you analyze the expected behavior of an algorithm on small random perturbations of the input data. In seminal work, Spielman and Teng published a notoriously difficult 94-page paper which proved that the simplex method is efficient in the smoothed analysis model.”

Highly complex jigsaw puzzle

Dadush met Sophie Huiberts when he was teaching a course on smoothed analysis during one of the MasterMath courses in mathematics in Utrecht, where Huiberts was studying. Already as a master student Huiberts got a room at CWI, which gave her the luxury to interact with all the colleagues there, and together Dadush and Huiberts took a fresh look at the work of Spielman and Teng.

Dadush: “We redid the entire analysis from scratch, looking at ways to make the analysis as elegant, simple and short as possible. Over time we started putting the pieces of this highly complex jigsaw puzzle together and managed to make significant improvements to the analysis.”

Sophie Huiberts giving a lecture at CWI. Picture: Léa Junger
Sophie Huiberts giving a lecture at CWI. Picture: Léa Junger

Spielman expressed great happiness with their results, and the work of Dadush and Huiberts was first published in a conference article (STOC 2018, one of two best TCS conference), an improved version got into a top journal (invited to the STOC special issue in SICOMP, 10 out of 112 papers), and they were invited to write a chapter in the book Beyond worst-case analysis of algorithms (edited by Tim Roughgarden). For her PhD thesis Geometric Aspects of Linear Programming, defended at Utrecht University, Huiberts received in 2023 the Stieltjes Prize for the best PhD thesis in mathematics defended in the academic year 2021/2022 at a Dutch university.

“Shedding light on the Simplex algorithm”, says Dadush, “is right at the intersection of mathematics and computer science: you have a real world algorithm and you have to define exactly the right mathematical model in which to analyze it correctly. So, our work is a perfect illustration of the synergy between the two fields that CWI wants to stimulate.”

While there is no direct practical impact of the new analysis by Dadush and Huiberts, the development of a better tool for analyzing the mysterious behavior of the Simplex algorithm definitely will open new possibilities for future applications. In 1991 pioneer George Dantzig already nicely summarized the societal impact of optimizing logistical problems: “The original problem that started my research is still outstanding, namely the problem of planning or scheduling dynamically over time, particularly planning dynamically under uncertainty. If such a problem could be successfully solved it could eventually through better planning contribute to the well-being and stability of the world.”

Author: Bennie Mols