Decompositie-algoritmen voor optimalisatieproblemen

Ondanks significante doorbraken in de combinatorische optimalisatie blijken algemene solvers nog altijd tekort te schieten om grote instanties van NP-harde problemen op te lossen. Voor deze open optimalisatievraagstukken biedt de ontwikkeling van probleemspecifieke (meta)heuristieken een uitweg. Dergelijke algoritmen, hoewel meestal erg performant, vergen een aanzienlijke ontwikkeltijd en zijn bijgevolg bijzonder duur.

Dit manuscript onderzoekt hoe decompositie-algoritmen een alternatief kunnen bieden voor zowel algemene solvers als probleemspecifieke heuristieken voor combinatorische optimalisatieproblemen. Een decompositie-algoritme benadert een probleem efficiënt door het op te splitsen in een aantal deelproblemen, die zelf gewoonlijk veel gemakkelijker zijn dan het oorspronkelijke optimalisatieprobleem. Met deze methodologie worden grote problemen alsnog oplosbaar met, bijvoorbeeld, algemene solvers.

Men kan decompositie-algoritmen als volgt categoriseren: algoritmen die het originele probleem optimaal oplossen en heuristische alternatieven die goede benaderende oplossingen berekenen. Terwijl dit onderzoek hoofdzakelijk decompositie-gebaseerde heuristieken bestudeert, komen de beide categorieën aan bod in het manuscript. De centrale onderzoeksvraag luidt ‘Kunnen deze decompositie-algoritmen de huidige probleemspecifieke (meta)heuristieken vervangen?’ Om deze vraag te beantwoorden onderzoekt dit werk zes verschillende logistieke problemen, gaande van scheduling tot rittenplanning. Bij elk van deze problemen horen uitdagende instanties, uitgebreid bestudeerd in de wetenschappelijke literatuur. Deze referentie-instanties vergemakkelijken een kwantitatieve performantievergelijking met bestaande algoritmen.

Het ontwerp van de verschillende decompositiestrategieën is ofwel geïnspireerd op de probleemstructuur of op veel eenvoudiger methoden die de probleemdimensies trachten te verminderen. Een grondige analyse van deze nieuwe decompositiebenaderingen bewijst de optimaliteit en de algemene toepasbaarheid van enkele algoritmen, die niettemin individuele probleemkarakteristieken aankunnen.

Het algemene raamwerk ontwikkeld tijdens dit onderzoek overstijgt de problemen in dit manuscript. Zonder noemenswaardige inspanning werd ook een ander optimalisatieprobleem uit de wetenschappelijke literatuur succesvol opgelost.

Uitgebreide computationele experimenten bevestigen de kwaliteit van de voorgestelde algoritmen, die talrijke nieuwe beste oplossingen laten noteren voor elk van de zes bestudeerde problemen. Deze thesis levert niet enkel een bijdrage tot elk individueel probleemdomein maar, bovenal, tot de decompositiemethoden van de toekomst.

De wetenschappelijke realisaties en praktische voordelen van decompositiege- baseerde algoritmen komen bijeen in een discussie over de rol van decompositie in actuele algoritmen voor combinatorische optimalisatieproblemen. In de geest van reproduceerbare wetenschap is de ontwikkelde broncode publiek beschikbaar, samen met de instanties en hun oplossingsbestanden.