42136 Optimering af store problemer med dekomposition

2025/2026

Kursusinformation
Large Scale Optimization using Decomposition
Engelsk
5
Kandidat
Kurset udbydes som enkeltfag
F2B (tors 8-12)
Campus Lyngby
Forelæsninger, øvelser og projektarbejde.
13-uger
F2B
Skriftlig eksamen og bedømmelse af opgave(r)
Skriftlig eksamen og en projektopgave (gruppearbejde). Opgaven er implementeringsorienteret og skal godkendes for at kunne deltage i den skriftlige eksamen. Opgaven er delt op i to afleveringer. Opgaven godkendes, hvis mindst 50% er besvaret korrekt. Opgaven tæller ikke med i kursuskarakteren.
Skriftlig eksamen: 4 timer
Alle hjælpemidler - uden adgang til internettet
7-trins skala , intern bedømmelse
42101.42114 , Introduktion til operationsanalyse (42101) og Heltals Programmering (42114) eller Netværks Optimering (42115) og mindst et andet OR-kursus
42112 , Programeringssproget Julia, med pakken Jump vil blive benyttet i øvelserne og afleveringsopgaver
Stefan Røpke , Lyngby Campus, Bygning 358, Tlf. (+45) 4525 4554 , ropke@dtu.dk
Richard Martin Lusby , Tlf. (+45) 4525 3084 , rmlu@dtu.dk
Fabricio Oliveira , fabol@dtu.dk
42 Institut for Teknologi, Ledelse og Økonomi
http://
I studieplanlæggeren
Dette kursus giver den studerende en mulighed for at lave eller forberede et projekt som kan deltage i DTUs studenterkonference om bæredygtighed, klimateknologi og miljø (GRØN DYST). Se mere på http://www.groendyst.dtu.dk
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:
  • Forstå og anvende dualitet i lineær programmering i metodeudvikling
  • Anvendelse af modeleringssoftware til implementere iterative algoritmer
  • Anvende Benders dekompositionsalgoritme
  • Anvende søjlegenereringsalgoritmen/​Dantzig-Wolfe dekomposition
  • Forstå korrektheden af Benders dekompositionsalgoritme og Dantzig-Wolfe dekompositionsalgoritme
  • Implementere basis udgaver af Benders dekompositionsalgoritme og Dantzig-Wolfe dekompositionsalgoritme
  • Analysere en matematisk model og vurdere, om den er egnet til dekompositionsmetoder
  • Opsummere og forklare en videnskabelig artikel om avancerede operationsanalysemetoder
Kursusindhold
Mange vigtige optimeringsproblemer kan modelleres ved hjælp af blandede heltalsprogrammeringsmodeller. Når sådanne modeller ikke kan løses med standardløsere, kan dekompositionsmetoder anvendes til at løse problemerne iterativt.

De centrale metoder omfatter:
- Benders dekompositionsalgoritme
- Søjlegenerering/​Dantzig-Wolfe-dekomposition

Kurset giver de studerende en grundig indføring i disse to typer dekompositionsalgoritmer og illustrerer, hvordan de kan anvendes på forskellige typer problemer.
Litteraturhenvisninger
Videnskabelige artikler og kursusnoter
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) til at implementere dekompositionsalgoritmerne. Studerende uden forhåndskendskab til Julia/JuMP må forvente en betydelig ekstra arbejdsindsats.
Sidst opdateret
05. december, 2025