VUB-prof wil de correctheid van combinatorische optimalisatiealgoritmes opvoeren tot 100 procent

VUB-prof wil de correctheid van combinatorische optimalisatiealgoritmes opvoeren tot 100 procent

Combinatorische optimalisatie gaat om het zoeken van een optimale (zo goed mogelijke) oplossing uit een zeer grote verzameling van mogelijke oplossingen. Het kan dan bijvoorbeeld gaan over praktische problemen zoals het zoeken van een uurrooster waarin zo weinig mogelijk overlap is, het zoeken naar routes voor verschillende postbodes om op zo kort mogelijke tijd alle pakketjes ter plaatse te brengen, soms ook over levensnoodzakelijke beslissingen zoals het koppelen van orgaandonoren aan patiënten waarbij zo veel mogelijk transplantaties kunnen plaatsvinden.

De technologie die naar dergelijke oplossingen zoekt is de laatste decennia enorm geëvolueerd en kan ondertussen met gemak vele problemen oplossen, waarbij er vaak miljarden mogelijke opties zijn. Maar toch ben je nooit helemaal zeker of de machine je de juiste oplossing heeft aangedragen. VUB-professor dr. Bart Bogaerts wil met zijn CertiFOX-project (Certified First-Order Model Expansion) een systeem uitdokteren waarbij die onzekerheden verdwijnen. Hij krijgt voor zijn onderzoek een ERC Consolidator Grant van Europa ter waarden van twee miljoen euro.

“Het centrale doel van mijn ERC-project is om methodologieën en hulpmiddelen te ontwikkelen waarmee we met honderd procent zekerheid kunnen garanderen dat het juiste probleem correct is opgelost”, zegt Bogaerts. “Omdat er bij complexe problemen soms vele mogelijke oplossingen zijn en je niet altijd kan controleren hoe een algoritme tot een bepaalde uitkomst is gekomen, willen we voortbouwen op recente doorbraken in het zogenaamde proof logging, waarbij algoritmes niet enkel een antwoord geven, maar ook een bewijs of certificaat van correctheid meeleveren.”

Een belangrijke beperking van de huidige technieken is dat de correctheid niet wordt bewezen in een voor ons begrijpbare taal, maar mits een low-level vertaling in computertaal, waardoor er nog altijd twijfel blijft bestaan over de correctheid van de geleverde oplossing. “In mijn project zullen we end-to-end garanties van correctheid onderzoeken”, aldus Bogaerts. “We willen hiervoor een hoog-niveau logische taal gebruiken die zowel voor mens als machine begrijpbaar is en garanderen dat het correctheidscertificaat uitgedrukt wordt in functie van input op dat hoge niveau. Als het lukt, zal het een grote invloed hebben op de manier waarop combinatorische optimalisatie-software ontwikkeld, geëvalueerd en gebruikt wordt: de bewijzen die geproduceerd worden zullen niet enkel debugging mogelijk maken, omdat bewijzen gedetailleerde informatie bevatten over waar bugs zijn opgetreden, maar evengoed de controleerbaarheid ten goede komen, omdat bewijzen opgeslagen en gecontroleerd kunnen worden door een onafhankelijke derde partij. Tot slot zal het uitmonden in een nauwkeurige evaluatie van algoritmische verbeteringen.”

Meer info:

Bart Bogaerts +32 2 629 37 06

https://bartbogaerts.eu/projects/CertiFOX/

 

 


Frans Steenhoudt
Frans Steenhoudt Perscontact wetenschap en onderzoek

 

WE IR
Over Press - Vrije Universiteit Brussel

volg ons op twitter @VUBrussel


De Vrije Universiteit Brussel is een internationaal georiënteerde universiteit in Brussel, het hart van Europa. Door het afleveren van hoogstaand onderzoek en onderwijs op maat, wil de VUB een actieve en geëngageerde bijdrage leveren tot een betere maatschappij.

De Wereld Heeft Je Nodig

De Vrije Universiteit Brussel neemt haar wetenschappelijke en maatschappelijke verantwoordelijkheid met liefde en daadkracht op. De VUB lanceerde daarom het platform ’De Wereld Heeft Je Nodig’.  Hier worden rond zes P’s ideeën, acties en projecten samengebracht, opgestart en uitgebouwd. De eerste P staat voor People, want daar draait alles om: mensen gelijke kansen geven, welvaart, welzijn, respect. Peace staat voor het bestrijden van klein en groot onrecht in de wereld. Prosperity gaat armoede en ongelijkheid te lijf. Planet staat voor acties rond biodiversiteit, klimaat, luchtkwaliteit, dierenrechten ... Met Partnership zoekt de VUB samenwerkingen om de wereld een betere plaats te maken. De zesde en laatste P is van Poincaré, de Franse filosoof Henri Poincaré aan wie de VUB haar leuze ontleent, dat het denken zich aan niets mag onderwerpen, behalve aan de feiten zelf. De VUB is een 'urban engaged university’, sterk verankerd in Brussel en Europa en werkend volgens de principes vrij onderzoek. www.vub.be/dewereldheeftjenodig

Press - Vrije Universiteit Brussel
Pleinlaan 2
1050 Brussel