Overordnede kursusmål
Målet med kurset er at give en grundig indføring i
dekompositionsalgoritmer. Dette skal gøre det muligt for de
studerende at anvende dekompositionsalgoritmer til at løse
komplekse optimeringsproblemer. Desuden trænes de studerende i at
anvende metoderne og implementere dem i Julia
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
- Beskrive motivationen for dekomponering i storskala optimering,
herunder blokstruktur, separabilitet og scenarie-baseret
modellering
- Forklare de grundlæggende idéer bag de centrale
dekomponeringsmetoder: Benders Decomposition, Dantzig–Wolfe
Decomposition, Stochastic Dual Dynamic Programming og Progressive
Hedging
- Redegøre for de matematiske fundamenter, der ligger til grund
for disse metoder, herunder dualitetsteori, konveksitet,
recourse-begrebet og value functions
- Formulere master- og delproblemer for deterministiske og
stokastiske optimeringsmodeller, der egner sig til
dekomponering
- Implementere grundlæggende versioner af Benders Decomposition,
Dantzig–Wolfe Decomposition, Stochastic Dual Dynamic Programming og
Progressive Hedging ved hjælp af et modelleringsværktøj (f.eks.
Julia/JuMP).
- Analysere en matematisk model med henblik på at afgøre, om den
besidder strukturelle egenskaber, der gør den egnet til
dekomponering
- Anvende dekomponeringsmetoder til at løse repræsentative
deterministiske og stokastiske optimeringsproblemer
- Sammenfatte de væsentligste fordele og begrænsninger ved de
behandlede metoder
Kursusindhold
Mange vigtige optimeringsproblemer kan formuleres som mixed integer
programming-modeller (MIP). Når sådanne modeller ikke kan løses
effektivt med standard løsningssoftware, kan
dekomponeringsalgoritmer anvendes til iterativt at løse problemet
ved at samle løsninger fra mindre delproblemer. De metoder, der
behandles i kurset, er Benders Decomposition, Dantzig–Wolfe
Decomposition/column generation, Stochastic Dual Dynamic
Programming (SDDP) og Progressive Hedging.
Kurset giver de studerende et grundigt overblik over disse metoder
og sætter dem i stand til at anvende dem som løsningsmetoder på
forskellige typer optimeringsproblemer.
Litteraturhenvisninger
Videnskabelige artikler, kursusnoter og bogen
"Branch-and-Price" af Jacques Desrosiers, Marco Lübbecke,
Guy Desaulniers, og Jean-Bertrand Gauthier. Bogen kan downloades
gratis på
https://link.springer.com/book/10.1007/978-3-031-96917-1
(når du er på DTU).
Bemærkninger
Kurset er kvantitativt orienteret, og en god forståelse af lineær
programmering er nødvendig. I øvelserne anvendes
programmeringssproget Julia/JuMP (som introduceres i kursus 42112)
samt SDDP-pakken til implementering af dekomponeringsalgoritmerne
Sidst opdateret
04. maj, 2026
