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.” Dat meldt de Universiteit Utrecht.
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 veelal commerciële software om optimalisatieproblemen op te lossen. Die software bestaat uit alsmaar evoluerende optimalisatie-algoritmes die steeds complexere problemen aankunnen.
Meetkundige structuur 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.
Oplossingen
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.
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.
Door: Nationale Onderwijsgids
Beeld: Harold van de Kamp
