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.
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.”
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.
