At give deltagerne en grundig indføring i problemformulering og
løsningsmetodik for heltalsprogrammeringsproblemer som disse opstår
i bl.a. trafik-, transport-, investerings- og
produktions-planlægning. Deltagerne bliver i stand til at formulere
heltalsprogrammeringer samt til at anvende en række af de simplere
optimeringsmetoder for disse.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
gennemføre simpel identifikation af løsningsmetoder for et
heltalsprogrammerings (IP) problem.
opstille en simpel heltalsprogrammering model med målfunktion,
begrænsninger og variabeldefinition ud fra en simpel tekst.
beskrive kontruktionen af en branch-and-bound (B&B)
algoritme for et standard IP problem.
gengive betydningen af og indholdet af de centrale beviser
indenfor netværk og heltalsprogrammering som angivet i kurset.
beskrive brugen af gyldige uligheder og snit generelt
ogspecifikt i forbindelse med et givet simpelt IP problem.
beskrive problemstillingerne ved udvidelsen fra uligheder og
snit til en branch-and-cut (B&C) algoritme.
opstille en dynamisk programmerings algoritme bestående af
"princple of optimality", "stage" og
"state" for et simpelt problem.
overordnet beskrive brugen af B&B, B&C, øvre og nedre
grænse ifm. en implementering af effektive løsningsmetoder for
simple IP problemer (herunder specielt TSP).
bruge Lagrange relaxering på et simpelt IP problem.
have en forståelse for værste-tids tidskompleksitet af en
algoritme.
Kursusindhold:
Branch & Bound, Snitplaner, Branch & Cut, Lagrange
relaksering, dynamisk programmering. Eksempler på anvendelser:
Projektplanlægning, rutelægning og produktionsplanlægning.
Litteraturhenvisninger:
L. Wolsey: Integer Programming, Wiley. Kursusnoter
Mulighed for GRØN DYST deltagelse:
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
