In 1947 vond George Dantzig het simplexalgoritme uit, dat nog steeds over de hele wereld veel wordt gebruikt voor optimalisatieprocessen: van het optimaliseren van mengvoeders tot vliegtuigbewegingen. Dit is een voorbeeld van een algoritme dat in de praktijk goed werkt, terwijl dat volgens de theorie niet altijd mogelijk is. Lange tijd begreep niemand dat. Sophie Huiberts - promovendus van het Centrum Wiskunde & Informatica (CWI) - en haar collega's vonden nieuwe theoretische oplossingen voor al lang openstaande problemen in dit vakgebied. Huiberts promoveerde 16 mei aan de Universiteit Utrecht op haar proefschrift ‘Geometric aspects of linear programming: shadow paths, central paths, and a cutting plane method’.
Waarom de software zo goed werkt
Voor softwareontwikkelaars en onderzoekers is het belangrijk welke algoritmes snel en welke langzaam zijn; het maakt het verschil uit tussen seconden of weken rekentijd. Een van de toepassingen is bijvoorbeeld planningssoftware waarmee processen worden geoptimaliseerd: van pakketbezorging en internationale supply chains tot het matchen van nierdonoren met patiënten. Een betere planning kan kosten verlagen en zorgen dat je betere resultaten haalt met de middelen die je hebt. Ondanks het belang hiervan is nog weinig bekend over waarom deze software zo goed werkt.
“In mijn onderzoek heb ik verschillende modellen bestudeerd en heb ik bepaalde praktische observaties kunnen omzetten in harde wiskunde”, zegt Huiberts. “In één project onderzochten we het effect van het toevoegen van een beetje willekeurige ruis aan de invoer van het zogeheten simplexalgoritme, een belangrijk onderdeel van alle software om ‘mixed integer programming’ problemen op te lossen . We konden bewijzen dat dit algoritme veel sneller is nadat er ruis is toegevoegd. Dit toevoegen van ruis gebeurde in de praktijk a; wij geven een nieuwe verklaring voor waarom dit werkt. Mijn onderzoek helpt belangrijke algoritmen voor het oplossen van lineaire programmeringsproblemen te begrijpen, waaronder de Simplexmethode, Inwendige Puntmethoden, en Snijvlakmethoden”.
Columbia University
Sophie Huiberts deed haar onderzoek in de Networks & Optimization groep van het Centrum Wiskunde & Informatica (CWI). Eerder studeerde ze wiskunde en informatica aan de Universiteit Utrecht en hierna wordt ze Junior Fellow van de Simons Society aan Columbia University in New York, USA. Tijdens het STOC 2021 event gaf Sophie Huiberts een internationale ‘Rising Star talk’, ze mocht deelnemen aan het Heidelberg Forum en zette zich als voorzitter van CWI’s ondernemingsraad onder meer in voor het stimuleren van diversiteit op de werkvloer. Ze ontwierp een browser plugin voor LaTeX op chatwebsite Slack, waarmee wiskundigen makkelijk kunnen communiceren en die 3500 gebruikers heeft.
Meer informatie
- Persoonlijke homepage van Sophie Huiberts
- Contactgegevens van Sophie Huiberts bij CWI
- Promotor: Prof. dr. G.L.M. Cornelissen (UU), copromotor: dr. D.N. Dadush (CWI), hoofd van CWI's Networks and Optimization groep
- De browser-plug-in van Sophie Huiberts om LaTeX te gebruiken op de chatwebsite Slack kan worden geïnstalleerd in Firefox of Chrome en de broncode is beschikbaar op Github. De plug-in heeft meer dan 3500 actieve gebruikers.
