Onderzoeksproject P7/36 (Onderzoeksactie P7)
Projectdomein
Combinatorische optimalisatieproblemen kunnen gedefinieerd worden als het zoeken naar een beste element in een eindige verzameling van elementen. Dit type van problemen is algemeen verspreid in onze hedendaagse globale gemeenschap. Een GPS toestel in onze wagen lost een combinatorisch optimalisatieprobleem op om de kortste route te vinden tussen een bron en een bestemming. Een software voor productieplanning bepaalt de optimale volgorde in dewelke goederen dienen geproduceerd te worden en wijst machines toe aan bepaalde productieloten. Transport- en koerier-bedrijven gebruiken combinatorische optimalisatie om te bepalen welk voertuig welke klanten zal bezoeken en in welke volgorde om de afgesproken deadlines te halen doch tegelijkertijd het brandstofverbuik te minimaliseren. Trein- en bus dienstregelingen, routes voor afhaling van huisafval en postbelevering worden opgesteld via combinatorische optimalisatie. Ditzelfde geldt voor het ontwerp van telecommunicatienetwerken en voor distributienetwerken voor gas, water en elektriciteit. Productie, distributie, telecommunicatie, bestuur, verkeer, economie, bio-informatica, milieuzorg, gezondheidszorg, financiering, het is moeilijk om een aspect van onze hedendaagse economie te vinden waarvan het ontwerp, het beheer en de controle niet berust op een oplossing van een of meer combinatorische optimalisatieproblemen.
Gegeven de algemene verspreiding van combinatorische optimalisatieproblemen, kan het belang van de ontwikkeling van efficiënte oplossingsmethoden voor zulke problemen niet worden overschat. Een breed spectrum van oplossingsmethoden voor combinatorische optimalisatieproblemen wordt aangeboden van exacte algoritmen tot een variëteit van heuristische benaderingen. Exacte algoritmen geven de waarborg om de optimale (d.w.z. de best mogelijke) oplossing te vinden, doch deze waarborg kan slechts gerealiseerd worden ten koste van uiterst lange rekentijden. Exacte methoden worden daarom veeleer gebruikt om kleine en relatief eenvoudige problemen op te lossen, of om een inzicht te verkrijgen in de wiskundige structuur van het optimalisatieprobleem. Aan de andere zijde van het spectrum, staan de heuristische oplossingsmethoden die geen waarborg bieden op een optimale oplossing, doch trachten een goede oplossing te vinden in een korte rekentijd. Met andere woorden, heuristische methoden offeren de waarborg om een optimale oplossing te vinden op ten voordele van het vinden van een goede oplossing in een beperkte beschikbare tijdsspanne.
Ook na enkele decennia onderzoek, blijven vele combinatorische optimalisatieproblemen een uitdaging voor de huidige optimalisatietechnieken. De overweldigende computerkracht die ons vandaag ter beschikking staat is een wonderbaarlijk hulpmiddel om de oplossing van zulke optimalisatieproblemen denkbaar te maken, doch ze is zelden voldoende om de complexiteit en grootte van vele combinatorische problemen uit de reële wereld aan te kunnen. De complexiteit van hedendaagse reële optimalisatieproblemen creëert een behoefte aan de ontwikkeling van vernieuwende methoden die op een efficiënte wijze de groeiende beschikbaarheid van rekenkracht kunnen benutten. Juist daarom, is de studie van combinatorische optimalisatieproblemen en de ontwikkeling van effectieve algoritmen voor de oplossing ervan een van de meest actieve onderzoeksdomeinen in de discipline van Operationeel Onderzoek. Heden ten dage kunnen enkel eenvoudige versies van kleine tot middelmatige grootte van vele problemen opgelost worden door middel van exacte methoden. Echter vele praktisch relevante problemen zijn in omvang groot en vertonen bovendien karakteristieken zoals de aanwezigheid van meervoudige doelstellingen, van dynamisch wijzigende gegevens, en van onzekere gegevens, die de oplossing van deze optimalisatieproblemen des te complexer maken. Alhoewel heuristieken in staat zijn om grote en complexe voorbeelden aan te pakken, vereisen zij nog steeds aanzienlijke rekentijden om tot een oplossing te komen en leveren zij oplossingen met behoorlijke verschillen tegenover de optimale oplossing.
Het strategische belang van van Operationeel Onderzoek, en Optimalisatie in het bijzonder, wordt geïllustreerd door een recent initiatief van LANCS, dat 12 miljoen Britse ponden aan fondsgelden tussen 2008 en 2013 toekende aan onderzoeksgroepen binnen dit vakgebied aan vier vooraanstaande Britse universiteiten.
Doelstellingen van het Project
De belangrijkste doelstellingen van het project zijn:
- Het samenbrengen van de beschikbare Belgische expertise op het gebied van combinatorische optimalisatieproblemen, synergie putten uit de samenwerking tussen de onderzoeksgroepen die als partners optreden, en een netwerk creëren met voldoende kritieke massa om jonge of ervaren wetenschappers op hoog niveau aan te trekken en financiering te verzorgen voor onderzoek in het domein.
- Het trainen van jonge onderzoekers in het domein van combinatorische optimalisatie. De vraag is immers hoog naar jonge mensen met dit profiel, zowel in academische onderzoekscentra als in de private sector.
- Het ontwerpen van nieuwe modellen, nieuwe algoritmische technieken en nieuwe vormen van implementatie voor complexe, grootschalige combinatorische optimalisatieproblemen.
- Het uitbouwen van internationale samenwerking met andere belangrijke teams die actief zijn op het gebied van combinatorische optimalisatie. De opzet van een actief en erkend Belgisch netwerk zal internationale samenwerking mogelijk maken, meer specifiek in het kader van grootschalige internationale projecten.
Het succesvol bereiken van deze doelstellingen zal leiden tot (i) een aantal belangrijke bijdragen op het vlak van fundamenteel onderzoek; (ii) een significante impact op de werking van verscheidene sectoren waarin deze combinatorische problemen optreden; en (iii) een aanzienlijk toegevoegde waarde tot de Belgische economie.
De Teams van het Project
De ontwikkeling van efficiënte methoden voor combinatorische optimalisatie is wereldwijd een erg actief onderzoeksdomein. Elk team dat aan dit project deelneemt heeft een duidelijke positionering in dit landschap: zij hebben een sterke internationale reputatie, zij hebben een uitstekende lijst van publicaties, en zij zijn actief op een internationaal niveau, zij het via internationale verenigingen (Mathematical Programming Society, EURO – the Association of European Operational Research Societies), of via de organisatie van internationale conferenties. De partners kennen elkaar goed en komen geregeld samen, o.a. op de jaarlijkse ORBEL conferentie. Bovendien hebben de partners van de Franstalige universiteiten een continue samenwerking via een project dat wordt gesubsidieerd door het FNRS en organiseren zij een jaarlijkse conferentie waarop doctoraatsstudenten en postdoctorale onderzoekers de mogelijkheid hebben om hun recent werk voor te stellen en nieuwe contacten te leggen.
De teams die deelnemen aan het project volgen een gezamenlijke aanpak om optimalisatieproblemen op te lossen: van de bouw van een wiskundig model ontsproten uit het onderliggende probleem tot de ontwikkeling van efficiënte oplossingsmethoden. Anders gezegd, zij delen een gezamenlijk standpunt hoe combinatorische problemen op te lossen en dus kan samenwerking tussen de teams op een naadloze wijze plaatsgrijpen. De onderzoeksteam zijn bovendien erg complementair wat betreft hun belangrijkste expertise. De specifieke sterkten van de teams worden weerspiegeld ofwel via de types van modellen die zij ontwikkelen (lineair vs. niet-lineair, continue vs. discrete variabelen, deterministische vs. stochastische aanpak, enkelvoudige vs. meervoudige doelstellingen), ofwel via de types van algoritmen die ze ontwerpen, ontwikkelen en implementeren (zij het exacte algoritmen of heuristische methoden), ofwel via het toepassingsgebied (supply chain management, telecommunicatie, transport, planning in diensten of productie, enz.).
Belangrijkste onderzoekslijnen
De belangrijkste onderzoekslijnen in het project zijn:
a) Bestudering en modellering van problemen: De vooruitgang in het gebied van combinatorische optimalisatie berust gedeeltelijk op de studie van de combinatorische structuur van de onderzochte problemen, alsook op de manier van modelleren. Combinatorische problemen kunnen klassiek geformuleerd worden als gemengd-geheeltallige lineaire optimalisatieproblemen. De formulering ervan kan echter versterkt worden door toevoeging van ongelijkheden. Een diepgaande kennis van types van efficiënte families van deze ongelijkheden heeft bewezen van cruciaal belang te zijn bij het oplossen van reële problemen. Ook de keuze van de ruimte voor de beslissingsvariabelen blijkt van groot belang om de problemen efficiënt op te lossen. Binnen deze context wenst het project de kennis van de problemen uit te diepen door de verschillende teams om tot betere ongelijkheden of tot sterkere formuleringen te komen.
b) Vooruitgang op het gebied van algoritmische technieken: vernieuwende bijdragen worden verwacht zowel op het gebied van exacte algoritmen als van heuristieken, doch vooral in de combinatie van beide technieken. Immers, algemeen wordt verwacht dat een doorbraak in combinatorische optimalisatie vanuit een integratie tussen exacte methoden en heuristieken zal plaatsgrijpen, en dit door de complementariteit van beide aanpakken uit te buiten. Een andere beloftevolle onderzoekslijn lijkt de combinatie van kunstmatige intelligentie-technieken met heuristieken. Voorbeelden zijn legio: het gebruik van machine learning en van beslissingstechnieken binnen heuristieken en van data mining om de invloed van probleemkarakteristieken te onderzoeken op het gedrag van algoritmen. De synergie tussen de partners zal uiterst nuttig zijn om in die richting te werken. Verder wordt verwacht dat vooruitgang wordt geboekt op het gebied van exacte algoritmen, bvb. door een diepgaande studie aangaande technieken voor decompositie en op het gebied van heuristieken, bvb. door een ontwerp van een generische methodologie voor het ontwikkelen van heuristieken.
C) Implementatie van oplossingsmethoden voor grootschalige, praktisch relevante problemen: Toepassingen voeden onderzoek en stellen eisen aangaande grotere of meer realistische optimalisatieproblemen. Toevoeging van meer details in een model leidt echter meestal tot een verhoging van het aantal beslissingsvariabelen en daardoor van de complexiteit van het optimalisatieprobleem. Zulke complexiteit wordt nog verhoogd indien meervoudige doelstellingen of dynamische wijzigende en onzekere data worden opgenomen in het probleem. Het project stelt als doel efficiënte implementaties voor dit type van grootschalige problemen te ontwikkelen, die optreden in toepassingen als productie, distributie, telecommunicatie, gezondheidszorg, economie en bio-informatica. Leden van de teams zijn reeds actief in verscheidene van deze toepassingsgebieden.
Concluderende Bemerking
Als besluit kan gesteld worden dat COMEX een verhoogde samenwerking tussen de teams toelaat en dat het project daardoor een aantal fundamentele bijdragen tot en doorbraken in het onderzoek kan maken en op deze wijze de sterkste excellentiepool op het gebied van combinatorische optimalisatie kan creëren. Bovendien zal deze pool een instrument vormen om internationale samenwerking aan te wakkeren en de zichtbaarheid van de teams internationaal te verhogen.
