Technisch Samenvatting: Een Numeriek Veilige Branch-Price-and-Cut Algoritme voor het Length-Constrained Cycle Partition Problem

1. Probleemdefinitie

Het Length-Constrained Cycle Partition Problem (LCCP) is een graafoptimalisatieprobleem gedefinieerd op een ongerichte graaf $G=(V, E)$. Het doel is om de verzameling knopen $V$ te partitioneren in het minimum aantal disjuncte cycli, zodanig dat elke knoop $i$ precies één keer wordt afgedekt.

Elke knoop $i$ is geassocieerd met een kritieke tijd $q_i > 0$, en elke zijde $\{i, j\}$ heeft een reistijd $t_{i,j} \ge 0$. Een cyclus $C$ is lengte-haalbaar als de totale reistijd niet de kritieke tijd van enige knoop die erin opgenomen is overschrijdt:
$$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$$
Het probleem staat bekend als NP-hard (reduceerbaar van het Traveling Salesman Problem) en laat geen algoritme toe dat in polynomiale tijd een benadering vindt. Eerdere state-of-the-art benaderingen maakten gebruik van compacte Mixed-Integer Programming (MIP) formuleringen (gebaseerd op Miller-Tucker-Zemlin of Subtour Elimination Constraints), die instanties tot 52 knopen konden oplossen.

2. Methodologie

De auteurs stellen een exact Branch-Price-and-Cut (BPC) algoritme voor gebaseerd op een Set Partitioning (SP) formulering.

2.1 Set Partitioning Formulering

In plaats van compacte formuleringen, wordt het probleem gemodelleerd als een set partitioning probleem waarbij variabelen volledige lengte-haalbare cycli vertegenwoordigen. De formulering minimaliseert $\sum_{C \in \Omega} \lambda_C \text{ onderworpen aan } \sum_{C \in \Omega} a^C_i \lambda_C = 1 \text{ voor alle } i \in V$. Vanwege de exponentiële grootte van $\Omega$, gebruiken de auteurs Column Generation om de Lineaire Programmering (LP) relaxatie dynamisch op te lossen.

2.2 Het Pricing Probleem (LCPCCP)

De kern van de computationele taak is het Length-Constrained Prize-Collecting Cycle Problem (LCPCCP), dat een cyclus met een negatieve gereduceerde kosten zoekt. Dit probleem is sterk NP-hard. De auteurs lossen dit op met behulp van:

• Dynamic Programming (DP): Een label-setting algoritme waarbij labels de bezochte knopen, gereduceerde kosten, totale reistijd en de minimale kritieke tijd van het pad bijhouden.
• Bidirectionale Zoektocht: Door gebruik te maken van de ongerichte aard van de graaf, breidt het algoritme labels vanuit een startknoop $s$ alleen uit tot $t(\ell) < q(\ell)/2$. Niet-gedomineerde labels van voorwaartse en achterwaartse zoektochten worden vervolgens samengevoegd om volledige cycli te vormen. Dit vermindert de zoekruimte aanzienlijk vergeleken met een monodirectionale zoektocht.
• Dominantieregels: Labels worden gepruned als een ander label op dezelfde knoop een lagere of gelijke gereduceerde kosten, een lagere of gelijke reistijd en een deelverzameling van de bezochte knopen heeft.
• ng-Relaxatie: Om niet-elementaire cycli (waarbij knopen opnieuw worden bezocht) af te handelen, gebruiken de auteurs een ng-pad relaxatie met dynamische buurtuitbreiding. Dit levert geldige lagere grenzen op terwijl de complexiteit van het strikt afdwingen van elementariteit tijdens de initiële zoekfasen wordt vermeden.
• Greedy Heuristiek: Eerst wordt een snelle heuristiek uitgevoerd om verbeterende cycli te vinden door negatieve duale knopen te verwijderen of positieve duale knopen toe te voegen, wat de noodzaak voor dure DP-iteraties vermindert.

2.3 Gebruik van Structuur

• Driehoeksongelijkheid: Voor knopen waar de driehoeksongelijkheid lokaal geldt, schakelen de auteurs over naar set covering constraints. Dit beperkt de duale variabelen tot niet-negatieve waarden, waardoor het verwijderen van zero-dual knopen tijdens pricing mogelijk is en preventief prunen wordt mogelijk gemaakt.
• Symmetrie Breken: Om te voorkomen dat dezelfde cyclus vanuit verschillende startknopen wordt gegenereerd, wordt de zoektocht beperkt tot het enkel bezoeken van knopen met kritieke tijden die groter dan of gelijk aan de startknoop zijn (met index tie-breaking).

2.4 Snijvlakken (Cutting Planes)

Het algoritme integreert twee families van snijvlakken:

• Subset Row Cuts (SRC's): Toegepast op deelverzamelingen van knopen om het aantal cycli te beperken dat hen beslaat.
• Clique Cuts (CC's): Gebaseerd op de conflictgraaf van de cycli.
  De auteurs onderzoeken het respecteren van deze snijvlakken binnen het pricing probleem. Ze stellen vast dat hoewel Clique cuts worden genegeerd in de pricing om complexiteit te vermijden, Subset Row cuts wel worden gerespecteerd door labels uit te breiden met extra resources, wat de convergentie op specifieke moeilijke instanties verbetert.

2.5 Numerieke Veiligheid

Een belangrijke bijdrage is de implementatie van numeriek veilige grenzen. Floating-point rekenkunde kan leiden tot onhaalbare duale oplossingen door afrondingsfouten. De auteurs stellen een dual repair mechanisme voor:

1. Schaal de floating-point dualen naar grote gehele getallen.
2. Verifieer de duale haalbaarheid exact met integer rekenkunde.
3. Indien onhaalbaar, verlaag de schaleringsfactor en probeer het opnieuw.
   Dit zorgt ervoor dat de lagere grenzen die gebruikt worden voor branching wiskundig rigoureus zijn, waardoor voorkomt dat het algoritme optimaliteit claimt op basis van numerieke artefacten.

2.6 Branching en Heuristieken

• Branching: Maakt primair gebruik van Edge Branching (het vastleggen van zijden om in of uit de oplossing te zitten). Ryan-Foster branching (op knoopparen) werd getest maar bleek minder robuust voor deze specifieke probleemstructuur.
• Heuristieken: Een branch-and-price variant van de heuristiek ontspant de dominantieregels om snel hoogwaardige primaire oplossingen te vinden, die vervolgens als warm starts worden gebruikt voor de exacte solver.

3. Belangrijkste Bijdragen

1. Set Partitioning Formulering: Toont aan dat een SP-gebaseerde aanpak aanzienlijk strakkere LP-relaxaties oplevert (gemiddelde root gap van 0,4%) vergeleken met eerdere compacte formuleringen (30,3% gap).
2. Bidirectionale DP Pricing: Introduceert een efficiënte bidirectionale zoektocht voor het LCPCCP pricing probleem, waarbij gebruik wordt gemaakt van de symmetrie van ongerichte grafen om de zoekruimte te verkleinen.
3. Numerieke Veiligheid: Biedt een raamwerk voor het verkrijgen van bewezen correcte lagere grenzen in een branch-and-price setting door floating-point solvers te combineren met exacte integer rekenkunde voor duale verificatie.
4. Algoritmische Integratie: Combineert greedy pricing, ng-relaxatie, symmetrie breken en specifieke cut management tot een samenhangende solver.

4. Computationele Resultaten

Het algoritme werd getest op 84 benchmark instanties (14 tot 100 knopen) tegen de vorige state-of-the-art branch-and-cut methode (bnc-sec).

• Prestaties: Het voorgestelde Branch-Price-and-Cut algoritme (specifiek de configuratie withsrc+pricing) loste 52 instanties op tot bewezen optimaliteit, vergeleken met 40 voor de vorige beste methode.
• Schaal: Het loste succesvol instanties op met tot wel 76 knopen, waarmee 14 voorheen onopgeloste instanties zijn opgelost. De vorige limiet was 52 knopen.
• Snelheid: De branch-and-price kern is gemiddeld 14,7 keer sneller dan de vorige beste aanpak.
• Root Node Efficiëntie: 49 van de 52 opgeloste instanties werden opgelost bij de root node zonder branching, wat de kracht van de LP-relaxatie benadrukt.
• Numerieke Veiligheid Overhead: De numeriek veilige versie loste hetzelfde aantal instanties op als de onveilige versie, maar was ongeveer 40% langzamer (7,6s vs 4,5s geometrisch gemiddelde). Echter, er werden geen incorrecte resultaten gedetecteerd in de onveilige versie, en de overhead wordt als gematigd beschouwd gezien de garantie van correctheid.

5. Betekenis en Claims

Het artikel claimt dat de set partitioning formulering de primaire drijfveer van prestaties is, wat strakke grenzen biedt die ervoor zorgen dat de meeste instanties bij de root node kunnen worden opgelost. De bidirectionale zoektocht en symmetrie breken worden geïdentificeerd als de meest impactvolle algoritmische componenten voor het verminderen van de runtime.

De auteurs merken bescheiden op dat hoewel de methode de state-of-the-art aanzienlijk verbetert, instanties voorbij 76 knopen onopgelost blijven, en de pricing routine de computationele bottleneck blijft. Ze suggereren dat toekomstige verbeteringen mogelijk sterkere duale grenzen of schaalbaardere pricing-algoritmen (bijv. GPU-acceleratie) vereisen. Het werk vestigt een nieuwe benchmark voor het oplossen van LCCP, waarbij wordt bewezen dat exacte methoden grotere, complexere instanties kunnen aanpakken wanneer ze worden gecombineerd met numeriek veilige, structuur-exploiterende technieken.