ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming

1. Probleemdefinitie

Tweestaps-stochastisch programmeren (2SP) is een fundamenteel raamwerk voor besluitvorming onder onzekerheid. Het model omvat:

• Eerste stap: Beslissingen ($x$) die worden genomen voordat de onzekerheid (realisatie van toevalsvariabele $\xi$) bekend is.
• Tweede stap (Recourse): Aanpassingsbeslissingen ($y$) die worden genomen nadat de onzekerheid is gerealiseerd, om de kosten te minimaliseren.

Het grootste probleem bij 2SP is de schaalbaarheid. Traditionele methoden zoals de Sample Average Approximation (SAA) vereisen het oplossen van een deterministische equivalent met een groot aantal scenario's, wat leidt tot enorme rekentijden. Bestaande machine learning-benaderingen, zoals Neur2SP, gebruiken neurale netwerken (NN) om de waarde-functie van de tweede stap te benaderen. Echter, het inbedden van standaard NN's (met ReLU-activaties) in een optimalisatieprobleem vereist Mixed-Integer Programming (MIP) formuleringen. Deze MIP-formuleringen introduceren binaire variabelen die de complexiteit exponentieel laten toenemen met de grootte van het netwerk, waardoor ze rekenkundig onhandelbaar worden voor grotere of diepere netwerken.

2. Methodologie: ICNN-verbeterde 2SP

De auteurs stellen ICNN-enhanced 2SP voor, een methode die Input Convex Neural Networks (ICNNs) gebruikt als surrogaatmodel voor de verwachte recourse-functie.

Kernprincipes:

• Convexiteit door Architectuur: ICNNs zijn architectonisch beperkt om convex te zijn ten opzichte van hun invoer (de eerste-staps beslissingen $x$). Dit wordt bereikt door niet-negatieve gewichten in de verborgen lagen en convexe, niet-dalende activeringsfuncties (zoals ReLU).
• Exacte Inference via LP: In tegenstelling tot standaard NN's, kan de inferentie van een getrainde ICNN worden omgezet in een Lineair Programmeren (LP) probleem. Dit is mogelijk omdat de ReLU-activatie lineair is en de convexiteitsbeperkingen de noodzaak voor binaire variabelen (voor het modelleren van de "knik" in ReLU) elimineren.
• Surrogaat Training: Het model leert de verwachte kosten $Q(x) = E_\xi[Q(x, \xi)]$ te voorspellen. Het gebruikt een encoder voor de scenario's (om de verdeling van $\xi$ te comprimeren) en een ICNN voor de mapping van beslissingen naar kosten.
• Reformulering: De oorspronkelijke 2SP wordt herschreven door de recourse-functie te vervangen door de ICNN. Omdat de ICNN convex is, kan deze exact worden ingebed in de eerste-staps optimalisatie als een LP-beperking, zonder binaire variabelen toe te voegen.

Theoretische Onderbouwing:
De paper analyseert wanneer de recourse-functie $Q(x)$ convex is:

1. Continue variabelen: $Q(x)$ is altijd convex (maximale functie van affiene functies via dualiteit).
2. Gemengd-integer eerste stap: $Q(x)$ blijft convex over het convex-hull van de eerste-staps beslissingen.
3. Gemengd-integer tweede stap: Hier is $Q(x)$ over het algemeen niet convex, maar vaak quasi-convex. De auteurs tonen aan dat ICNNs deze quasi-convexe structuren in de praktijk effectief kunnen benaderen, vooral wanneer de overgangen tussen convex regimes glad zijn.

3. Belangrijkste Bijdragen

1. Eliminatie van Integer Variabelen: De belangrijkste bijdrage is het vervangen van de MIP-formulering (nodig voor standaard NN's) door een zuivere LP-formulering door gebruik te maken van ICNNs. Dit elimineert de combinatorische complexiteit die inherent is aan MIP.
2. Eerste Integratie van ICNN in 2SP: Het paper introduceert het eerste raamwerk dat ICNNs specifiek toepast voor het benaderen van de verwachte recourse-functie in 2SP-problemen, waarbij de convexiteit van het probleem wordt benut.
3. Scalabiliteit en Efficiëntie: De methode biedt een schaalbaar alternatief dat de oplossingstijden drastisch verkort, vooral voor grote probleemgroottes, terwijl de oplossingskwaliteit behouden blijft.

4. Resultaten

De auteurs hebben hun methode getest op drie standaard benchmarkproblemen:

• Capacitated Facility Location Problem (CFLP)
• Stochastic Server Location Problem (SSLP)
• Investment Problem (INVP)

De resultaten worden vergeleken met Neur2SP (standaard NN + MIP) en de Extensive Form (EF) (exacte oplossing, vaak onhaalbaar voor grote schalen).

• Trainingsprestaties: ICNNs vereisen slechts marginale extra tijd voor training (ongeveer 10% langer) vergeleken met standaard NN's, maar behalen vergelijkbare of zelfs betere validatie-accuraatheid (lagere MAE) in de meeste gevallen. Dit suggereert dat de recourse-functies in deze benchmarks goed benaderbaar zijn door convexe functies.
• Oplossingstijd (Solving Time):
  • ICNN-enhanced 2SP is aanzienlijk sneller dan Neur2SP. Voor complexe instanties (bijv. CFLP_50_50) worden snelheidsverhogingen van tot wel 100x bereikt.
  • Waar Neur2SP vaak de tijdslimiet (3 uur) bereikt, lost de ICNN-methode deze problemen op in seconden.
  • Voor de meest uitdagende instanties (grote scenario-aantallen) faalt de EF-methode vaak om een oplossing van vergelijkbare kwaliteit te vinden binnen de tijdslimiet, terwijl de ICNN-methode dit wel doet.
• Oplossingskwaliteit: De oplossingskwaliteit (gemeten als optimality gap ten opzichte van de EF of beste bekende oplossing) is vergelijkbaar met of beter dan Neur2SP. In 80% van de gevallen levert de ICNN-methode een gelijke of superieure kwaliteit op.
• Formulatiegrootte: De LP-formulering van de ICNN vereist geen binaire variabelen en ongeveer de helft van de hulpvariabelen in vergelijking met de MIP-formulering van Neur2SP, wat leidt tot een veel compactere wiskundige formulering.

5. Betekenis en Conclusie

Deze studie biedt een cruciale doorbraak in het oplossen van tweestaps-stochastische optimalisatieproblemen. Door de architecturale convexiteit van ICNNs te benutten, wordt de barrière van de MIP-complexiteit doorbroken.

• Praktische Toepasbaarheid: De methode maakt real-time of tijdskritische besluitvorming mogelijk in sectoren zoals energiedistributie en productieplanning, waar frequente herberekeningen nodig zijn en MIP-oplossers te traag zijn.
• Complementair aan Neur2SP: De methode is ideaal voor problemen met convexe of quasi-convexe recourse-functies. Voor sterk niet-convexe problemen blijft Neur2SP (MIP) nodig, maar voor een breed scala aan praktische toepassingen (zoals voorraadbeheer en portfolio-optimalisatie) biedt ICNN-enhanced 2SP een superieur, schaalbaar alternatief.
• Toekomstperspectief: Het werk opent de deur voor verdere onderzoek naar hybride architecturen en de toepassing van ICNNs in niet-lineaire convexe omgevingen, wat de brug slaat tussen convex optimalisatie en diep leren voor betrouwbare besluitvorming onder onzekerheid.