Ondanks decennia van explosieve groei in rekenkracht, ondanks veel meer en diepere wiskundige en computerwetenschappelijke kennis, ondanks veel meer wetenschappers die werken aan algoritmen, is een algoritme uit 1947 nog steeds het meest succesvol voor het optimaliseren van logistieke problemen. Het wordt op grote schaal toegepast op gebieden variërend van productie en transport tot telecommunicatie. En het mysterie is dat niemand theoretisch kan onderbouwen waarom dit algoritme zo succesvol is in de praktijk. Maar de afgelopen jaren hebben CWI-onderzoekers meer licht op de zaak kunnen werpen, voortbouwend op eerder werk van Amerikaanse wiskundigen.
Simplex-methode
Het algoritme in kwestie is het Simplex-algoritme, bedacht door de Amerikaan George Dantzig (1914-2005), die beschouwd wordt als een van de grondleggers van lineair programmeren. Over het succes van de Simplex methode zei Dantzig in 1982: "De enorme kracht van de methode blijft me verbazen."
CWI-onderzoeker Daniel Dadush, leider van de groep Networks & Optimization, realiseerde zich dat het zoeken naar een verklaring voor het langdurige succes zeer risicovol onderzoek was waar wel hoge winst uit te behalen viel als het lukte. Samen met Sophie Huiberts, die eerst als masterstudent en later als promovendus werkte, besloot hij het risico te nemen, in de geest van de langetermijnmissie van CWI.
Dadush: "Om verder te gaan dan worst-case analyse ontwikkelden computerwetenschappers Daniel Spielman en Shang-Hua Teng een model dat smoothed (afgevlakte) analyse wordt genoemd, waarbij je het verwachte gedrag van een algoritme analyseert op kleine willekeurige verstoringen van de invoergegevens. In hun baanbrekende werk publiceerden Spielman en Teng een notoir moeilijk 94 pagina's tellend artikel dat bewees dat de Simplex-methode efficiënt is in het afgevlakte analysemodel."
Zeer complexe legpuzzel
Dadush ontmoette Sophie Huiberts toen hij een cursus over smoothed analyse gaf tijdens een van de masteropleidingen wiskunde in Utrecht, waar Huiberts studeerde. Als masterstudent kreeg Huiberts al een kamer in het CWI, wat haar de luxe gaf om met alle collega's daar samen te werken. Vervolgens namen Dadush en Huiberts het werk van Spielman en Teng onder de loep.
Dadush: "We herwerkten de hele analyse vanaf nul en keken naar manieren om de analyse zo elegant, eenvoudig en kort mogelijk te maken. Na verloop van tijd begonnen we de stukjes van deze zeer complexe legpuzzel in elkaar te passen en slaagden we erin om de analyse aanzienlijk te verbeteren."
Spielman liet weten erg blij te zijn met hun resultaten, en het werk van Dadush en Huiberts werd voor het eerst gepubliceerd in een conferentieartikel (STOC 2018, een van de twee beste TCS-conferenties). Een verbeterde versie kwam in een toptijdschrift (de STOC special issue in SICOMP, waarvoor 10 van de 112 papers werden geselecteerd), en ze werden uitgenodigd om een hoofdstuk te schrijven in het boek Beyond worst-case analysis of algorithms (geredigeerd door Tim Roughgarden). Voor haar proefschrift Geometric Aspects of Linear Programming, verdedigd aan de Universiteit Utrecht, ontving Huiberts in 2023 de Stieltjesprijs voor het beste proefschrift in de wiskunde verdedigd in het academisch jaar 2021/2022 aan een Nederlandse universiteit.
