Learning to Cut: Reinforcement Learning for Benders Decomposition

Technische Samenvatting: Leren Snijden: Versterkend Leren voor Benders Decompositie

Probleemstelling
Benders Decompositie (BD) is een standaardaanpak voor het oplossen van tweestaps-stochastische programma's, die besluitvorming onder onzekerheid modelleren door "hier-en-nu"-beslissingen in de eerste fase te scheiden van "wachten-en-kijken"-herstelacties in de tweede fase. Hoewel effectief, lijdt klassieke BD vaak aan trage convergentie. Deze inefficiëntie vloeit voort uit een afweging in het beheer van snijvlakken: het toevoegen van alle scenario-specifieke snijvlakken (meervoudige snijvlakformulering) creëert een strakkere benadering van de herstelwaardefunctie, maar vergroot het hoofddeelprobleem aanzienlijk, wat de daaropvolgende oplossingen vertraagt; omgekeerd houdt het aggregeren van snijvlakken tot één enkel snijvlak (enkele snijvlakformulering) het hoofddeelprobleem klein, maar levert zwakkere benaderingen op. Bestaande heuristische benaderingen, zoals het selecteren van alleen de meest geschonden snijvlakken of het gebruik van Pareto-optimale snijvlakken, proberen dit te beheersen, maar ze vertrouwen vaak op deterministische regels die zich mogelijk niet goed aanpassen aan variërende probleemstructuren of gegevensinvoer.

Methodologie
De auteurs stellen Versterkend Leren voor BD (RLBD) voor, een kader dat de selectie van snijvlakken modelleert als een sequentiële besluitvormingsprobleem binnen een Markov-besluitproces (MDP) met een eindige horizon en discontering.

• MDP-vormgeving:

  • Staatruimte ($S$): De staat bij elke iteratie $t$ vat zowel globale convergentiestatistieken (iteratie-index, onder-/bovengrenzen, optimaliteitskloof, kloofreductiesnelheden, en oplostijden voor het hoofddeel- en deelsubprobleem) als lokale kenmerken van snijvlakken samen. Lokale kenmerken voor elk kandidaat-snijvlak omvatten schendingniveaus, normen van duale variabelen, coëfficiënten van snijvlakken, en de historische frequentie van snijvlakken gegenereerd door hetzelfde scenario.
  • Actieruimte ($A$): De actie bestaat uit het selecteren van een subset van $K$ kandidaat-snijvlakken uit de beschikbare scenario-specifieke snijvlakken om toe te voegen aan het hoofddeelprobleem.
  • Beloningsfunctie ($r$): De beloning is een gewogen som van drie componenten: (1) een op de kloof gebaseerde term die de logaritmische reductie in de optimaliteitskloof weerspiegelt (convergentie aanmoedigen), (2) een negatieve term evenredig met de oplostijd van het hoofddeelprobleem (efficiëntie aanmoedigen), en (3) een straf per stap (kortere trajecten aanmoedigen).
  • Overgangsdynamiek: De omgeving gaat over naar de volgende staat door het bijgewerkte hoofddeelprobleem op te lossen met de geselecteerde snijvlakken, nieuwe deelsubproblemen te genereren, en nieuwe grenzen en statistieken te berekenen.

• Parameterisering van het Beleid en Training:

  • Het beleid voor snijvlakselectie $\pi_\theta$ wordt geparametriseerd door een gedeeld feedforward-neuraal netwerk. Het netwerk verwerkt een samengevoegde vector van globale staatinformatie en lokale kenmerken van snijvlakken voor elk kandidaat-snijvlak, en geeft een scalair logit uit. Een softmax-functie converteert deze logits naar een kansverdeling.
  • Het beleid wordt getraind met het REINFORCE-algoritme (een methode voor beleidsgradiënten). Tijdens trainingsepisoden steekt de agent een reeks van $K$ snijvlakken zonder teruglegging op basis van de huidige beleidsverdeling. De beleidsparameters worden bijgewerkt via gradiëntstijging om de verwachte cumulatieve gediskonterende beloning te maximaliseren.
  • Inferentie: Tijdens het testen wordt het getrainde beleid op een greedige manier toegepast, waarbij de top-$K$ snijvlakken met de hoogste logits voor elke nieuwe probleeminstantie worden geselecteerd.

Belangrijkste Bijdragen

1. Stochastisch Beleid voor Snijvlakselectie: In tegenstelling tot deterministische heuristieken, hanteert RLBD een stochastisch beleid dat selectiekansen toekent op basis van zowel globale algoritmische vooruitgang als lokale kenmerken van snijvlakken. Dit stelt de agent in staat om informatieve snijvlakken te benutten, terwijl het vermogen behouden blijft om alternatieve kandidaten te verkennen die later kritiek kunnen worden.
2. Generaliserend Vermogen: Het kader is ontworpen om te generaliseren naar problemen met vergelijkbare structuren maar variërende gegevensinvoer (bijvoorbeeld verschillende realisaties van vraag) en dimensies van beslisvariabelen (bijvoorbeeld verschillende aantallen faciliteiten of klanten), zonder hertraining.
3. Prestatieverbeteringen: De aanpak toont aanzienlijke verbeteringen ten opzichte van bestaande benchmarks, waaronder vanilla BD en LearnBD (een benadering met toezicht op leren met behulp van Support Vector Machines).

Experimentele Resultaten
De auteurs hebben RLBD geëvalueerd op een tweestaps-stochastisch probleem voor de locatie van laadstations voor elektrische voertuigen (EV). De experimenten omvatten training op een specifieke instantie en testen op instanties met variërende probleemgroottes ($8\times12$, $10\times15$, $20\times30$) en vraagverdelingen (Normaal, links-scheef en rechts-scheef).

• Kleine tot Middelgrote Instanties: Voor instanties met $8\times12$ en $10\times15$ configuraties bereikte RLBD een reductie in rekentijd van ongeveer vijf keer in vergelijking met vanilla BD en LearnBD, terwijl vergelijkbare optimaliteitskloven werden behouden. Deze winst in efficiëntie werd voornamelijk toegeschreven aan de adaptieve selectie van snijvlakken, wat resulteerde in aanzienlijk kortere oplostijden voor het hoofddeelprobleem.
• Grote Instanties: Voor grotere instanties ($20\times30$), waarbij alle methoden faalden om binnen het tijdslimiet van één uur te convergeren, bereikte RLBD een kleinere uiteindelijke optimaliteitskloof (ongeveer 28–29%) in vergelijking met de benchmarks (ongeveer 35–39%).
• Gevoeligheid voor Hyperparameters: De studie identificeerde dat een beloningsgewicht van $\alpha=0.01$ (kloofreductie) en $\lambda=0.001$ (straf per stap), gecombineerd met het toevoegen van $K=10$ snijvlakken per iteratie, de meest stabiele convergentie en efficiëntie opleverde.
• Beheersinzichten: Analyse van het geleerde beleid onthulde dat het de voorkeur geeft aan snijvlakken uit scenario's met een hogere totale vraag, blootstelling aan boetes en blootstelling aan omzet, wat suggereert dat het model realisaties met hoge belasting succesvol identificeert als kritiek voor het strakker maken van de formulering.

Betekenis en Claims
Het artikel claimt dat RLBD een robuust, adaptief alternatief biedt voor traditionele strategieën voor het beheer van snijvlakken. Door de selectie van snijvlakken te kaderen als een leerprobleem, overwint de methode de starheid van deterministische heuristieken. De auteurs benadrukken dat het getrainde beleid sterke generalisatie vertoont, effectief omgaat met verdelingsverschuivingen en veranderingen in probleemdimensies zonder hertraining te vereisen. De resultaten suggereren dat het integreren van versterkend leren in de BD-lus de computationele efficiëntie voor tweestaps-stochastische programma's aanzienlijk kan verbeteren, met name in scenario's waar de grootte van het hoofddeelprobleem een knelpunt wordt. Het werk positioneert RLBD als een haalbare methode om de schaalbaarheid van stochastische optimalisatie te verbeteren in real-world toepassingen zoals locatie van faciliteiten en supply chain management.