Daniel Dadush benoemd tot hoogleraar Geometry of Optimization

Daniel Dadush is benoemd tot deeltijdhoogleraar Geometry of Optimisation aan het Mathematisch Instituut van de Universiteit Utrecht. Dadush is daarnaast onderzoeker en groepsleider van de Networks and Optimization onderzoeksgroep aan het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Met de leerstoel wil de universiteit de maatschappelijke impact van het onderzoeksveld vergroten, door meer samenwerking met Utrechtse informatici.

Optimalisatieproblemen zijn overal

Overal ter wereld vind je optimalisatieproblemen: van internationale distributie-ketens en planningen in het openbaar vervoer tot het matchen van donororganen. Het vinden van de beste oplossing voor een optimalisatieprobleem is vaak ingewikkeld en tegelijkertijd belangrijk: het ideale antwoord kan miljoenen euro’s aan winst of een significante vermindering van CO2-uitstoot opleveren. Bedrijven gebruiken tegenwoordig vaak commerciële software om optimalisatieproblemen op te lossen. Die software bestaat uit almaar evoluerende optimalisatie-algoritmes die steeds complexere problemen aankunnen.

Geometrie van optimalisatieproblemen

Daniel Dadush richt zich in zijn onderzoek op het benutten van de meetkundige structuur van optimalisatieproblemen. Als we steeds complexere problemen willen kunnen oplossen, dan is het wat hem betreft essentieel om die structuur beter te begrijpen.  

De oplossingen voor optimalisatieproblemen kunnen in veel gevallen worden voorgesteld als punten op de rand, of binnenin, een hoog-dimensionaal object. Deze objecten heten polytopen. Het idee is dat een computeralgoritme de optimale oplossing snel kan vinden door de geometrische eigenschappen van een polytoop te gebruiken.

Figuur 1 is een weergave van het bekende simplexalgoritme voor het oplossen van lineaire optimalisatieproblemen. De hoekpunten van de polytoop representeren alle mogelijke oplossingen voor het optimalisatieprobleem. Het algoritme zoekt langs de randen naar het hoekpunt dat de meest optimale oplossing vertegenwoordigt.

Figuur 2 is een weergave van een integer-algoritme voor het oplossen van discrete optimalisatieproblemen. Deze algoritmes modelleren problemen waarbij de variabelen alleen gehele waarden mogen aannemen, zoals hoeveel chauffeurs er voor een bezorgroute zijn, of hoeveel containers gebruikt mogen worden om goederen te verschepen. Deze wijze van programmeren wordt veel gebruikt voor het oplossen van problemen in de transport, logistiek en de gezondheidszorg.

Paradox oplossen: de efficiëntie van het simplexalgoritme

De wetenschappelijke carrière van Dadush bereikte een mijlpaal toen zijn werk er mede voor zorgde dat een mysterie rondom het veelgebruikte simplexalgoritme kon worden ontrafeld. Dit algoritme is in de praktijk zeer efficiënt, maar er zijn eenvoudige voorbeelden waarbij het algoritme een exponentieel aantal hoekpunten langsgaat. In echte situaties is dat helemaal niet mogelijk. Deze paradox heeft onderzoekers jarenlang beziggehouden. In samenwerking met Sophie Huiberts (die haar promotieonderzoek onder supervisie van Dadush deed bij het CWI en de UU en nu onderzoeker is bij het Franse Nationale Centrum voor Wetenschappelijk Onderzoek), hielp hij dit raadsel op te lossen.

Dit deden Dadush en Huiberts door de schattingen te verbeteren die de methode smoothed analysis maakt. Dit is een krachtige methode die het praktische gedrag van algoritmen, zoals het simplexalgoritme, verklaart. De schattingen laten zien hoe het algoritme zich gedraagt bij kleine veranderingen in de data waarmee het werkt. Met hun werk toonden Dadush en Huiberts aan dat het simplexalgoritme veel nauwkeuriger schattingen maakt dan wetenschappers voorheen dachten. De Franse krant Le Monde publiceerde een uitgebreid artikel over de ontdekking.

Krachten bundelen

Op het CWI is Daniel Dadush de groepsleider van de Networks and Optimization onderzoeksgroep. Een belangrijke missie van zijn nieuwe leerstoel is nauwe samenwerking met informatici van de Algorithms and Complexity Group aan de Universiteit Utrecht. "De mogelijkheden zijn enorm wanneer we onze krachten bundelen”, meent Dadush. Hij doelt op de wiskundige precisie en de theoretische basis vanuit zijn eigen vakgebied en de praktische, probleem-oplossende expertise vanuit de computerwetenschap. De samenwerking overbrugt niet alleen de kloof tussen theorie en praktijk, maar stimuleert ook innovatie, vindt hij. En dat leidt tot de ontwikkeling van efficiënte algoritmes die een behoorlijke impact kunnen hebben op de maatschappij.

Portretfoto van Daniel Dadush: ©Universiteit Utrecht. Bron: nieuwsbericht over Daniel Dadush's hoogleraarschap op de UU website.

Zie ook Daniel Dadush's contactgegevens op het CWI.