English | Log ind

42136 Optimering af store problemer med dekomposition

2019/2020

Kursus i avancerede dekompositions algoritmer som anvendes til løsning
af store heltals lineære programmer til optimalitet. Under kurset lærer den studerende både teorien og implementerer algoritmerne på svære problemer.
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
Mundtlig eksamen og bedømmelse af rapport(er)
1 rapport og mundtlig eksamen i rapporten og teorien bag. Ændringer som følge af COVID-19: Den mundtlige eksamen aflyses og evaluering foretages på baggrund af rapporten. Rapporten indeholder elementer af gruppearbejde og en individuel del.
Alle hjælpemidler er tilladt
7-trins skala , intern bedømmelse
42132
42101.42114 , Introduktion til operationsanalyse (42101)og Heltals Progrrammering (42114) eller Netværks Optimering (42115) og mindst eet andet OR-kursus
42112 , Programerings sproget Julia, med pakken Jump vil blive benyttet i øvelserne og afleveringsopgaver
Minimum 15
Thomas Jacob Riis Stidsen , Lyngby Campus, Bygning 358, Tlf. (+45) 4525 4449 , thst@dtu.dk
Stefan Røpke , Lyngby Campus, Bygning 358, Tlf. (+45) 4525 4554 , ropke@dtu.dk
Richard Martin Lusby , rmlu@dtu.dk
42 Institut for Teknologi, Ledelse og Økonomi
http://
I studieplanlæggeren
Overordnede kursusmål
Målet med kurset er at give en grundig indføring i dekompositions algoritmer. Dette skal gøre det muligt for de studerende at anvende dekompositions algoritmer til at løse komplekse optimerings problemer. Desuden trænes den studerende i at anvende metoderne og implementere disse i Julia
Læringsmål
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
  • Analysere matematiske optimerings modeller.
  • Forstå og anvende lineær programmerings dualitet i metode udvikling.
  • Anvendelse af modeleringssoftware til implementere iterative algoritmer
  • Forstå og anvende nedregrænse metoder.
  • Dekomponere matematisk modeller så disse kan løses iterativt.
  • Anvende Benders dekompositions algoritme.
  • Anvende Søjle genererings algoritmen/Dantzig-Wolfe dekomposition.
  • Forstå korrektheden af Benders dekompositions algoritme og Dantzig-Wolfe dekomposition algoritme
  • Implementere basis udgaver af Benders dekompositions algoritme og Dantzig-Wolfe dekompositions algoritme
Kursusindhold
Mange vigtige optimerings problemer kan modelleres vha.blandet heltals programmerings modeller. Når disse ikke kan løses med standard løsere, kan dekompositions metoder anvendes til at løse problemerne iterativt. Metoderne er:
- Benders dekompositions algoritme
- Søjle generering/Dantzig-Wolfe dekomposition

Kurset giver den studerende en grundig indføring i de to typer af dekomponerings algoritmer og illustrere anvendelsen af dem til diverse problemer.
Litteraturhenvisninger
Kursusnoter
Bemærkninger
Kurset er kvantitativt orienteret og en god forståelse af lineær programmering er nødvendig. I øvelserne vil der blive benyttet computer sproget Julia/JuMP (som der undervises i i kurset 42112) til at implementere dekompositions algoritmerne. Studerende uden Julia/JuMP kendskab skal forberede sig på en betydelig ekstra arbejdsindsats.
Sidst opdateret
21. april, 2020