Daniel Dadush benoemd tot hoogleraar Geometry of Optimisation

Het College van Bestuur van de Universiteit Utrecht heeft Daniel Dadush benoemd tot deeltijdhoogleraar Geometry of Optimisation aan het Mathematisch Instituut. Dadush is daarnaast onderzoeker 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. Dadush: "De mogelijkheden zijn enorm wanneer we onze krachten bundelen.”

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 CO²-uitstoot opleveren. Bedrijven gebruiken tegenwoordig veelal commerciële software om optimalisatieproblemen op te lossen. Die software bestaat uit alsmaar evoluerende optimalisatie-algoritmes die steeds complexere problemen aankunnen.

Geometrie van optimalisatieproblemen

Professor 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 zijn voor een bezorgroute, 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 Du Monde publiceerde een uitgebreid artikel over de ontdekking.

Krachten bundelen

Een belangrijke missie van deze 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.