Distributed Stochastic Programming with Applications to Large-Scale Hydropower Operations

QC 20211108

Abstract

Stokastisk programmering är ett område inom optimeringslära som behandlar beslutsproblem under osäkerhet. Ingenjörsproblem som innehåller slumpmässiga element kan modelleras noggrant med stokastiska program. Planering av vattenkraftsdrift är en specifik tillämpning som har motiverat mycket av arbetet i den här avhandlingen. Komplexa beslutsproblem leder ofta till stokastiska programmeringsproblem vars storlek överskrider kapaciteten hos moderna persondatorer. Det behövs därför skalbara beräkningsmetoder som kan exekveras i en distribuerad miljö bestående av flera samverkande datorer. I denna avhandling utvecklar vi matematiska metoder och beräkningsverktyg som kan användas för att representera och lösa distribuerade stokastiska program effektivt.

  I den första delen av avhandlingen presenterar vi ett ramverk för stokastisk programmering som implementerats i programmeringsspråket Julia. En nyckelfunktion i ramverket är möjligheten att instansiera distribuerade stokastiska program. Ramverket innehåller också en uppsättning optimeringsalgoritmer för att lösa stokastiska program genom att utnyttja problemens struktur. Dessa algoritmer är baserade på metoderna ``L-shaped'', ``progressive-hedging'', och ``quasi-gradient'' och kan appliceras parallellt på distribuerade stokastiska program. Vi presenterar algoritmiska innovationer och designmönster som ger förbättrad prestanda i distribuerade miljöer. Vi redogör även för programpaketes struktur och belyser viktiga detaljer i implementationen. Vi demonstrerar slutligen ramverkets funktionalitet med enkla exempel och tillhandahåller prestandatester utförda på storskaliga problem.

  I följande kapitel fortsätter vi med att undersöka förbättringar av den distribuerade L-shaped metoden. Speciellt undersöker vi dynamisk snittaggregering. Vi utvecklar teori som beskriver algoritmens konvergens och komplexitet och genom numeriska experiment visar vi sedan prestandaförbättringar. Vi föreslår olika aggregeringstrategier baserade på parametriserade urvalsregler. Snittaggregering kan avsevärt förbättra prestandan hos distribuerade L-shaped algoritmer.

  Sedan undersöker vi en slätningsmetod för storskalig stokastisk programmering. We härleder en slät approximation av subproblemen i kvasigradientalgoritmen, vilket låter oss bruka moderna acceleringsmetoder för gradientbaserade algoritmer. We härleder problemberoende approximationsgränser  och konvergensegenskaper och noterar en avvägning mellan noggrannhet och lösningshastighet. We föreslår sedan en hybrid metod som är både snabb och noggrann och visar att den är konkurrenskraftig jämfört med L-shaped i storskaliga experiment.

  Slutligen applicerar vi våra beräkningsmetoder på beslutsproblem från vattenkraftsindustrin. Vi studerar tre fallstudier kring Skellefteälven. Det första problemet berör budstrategier för en vattenkraftsproducent som deltar på en avreglerad elmarknad. Målet är att bestämma optimala bud på en spotmarknad innan marknadspriset är fastställt och sedan optimera kommande dags vattenkraftsproduktion. Vi ger en detaljerad beskrivning av budgivningsproblemet och förklarar sedan hur modellen kan implementeras i vårat ramverk. Genom att använda en stickprovsbaserad metod, som bygger på våra strukturnyttjande algoritmer, så kan vi beräkna ett konfidensintervall kring budgivningsproblemets optimala värde med hög precision. Sedan undersöker vi en version av budgivningsproblemet där vi även schemalägger förebyggande underhåll av kraftstationerna. Slutligen ställer vi upp ett kapacitetsexpansionsproblem med lång planeringshorisont.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-304522