42114 Heltalsprogrammering
2017/2018
Overordnede kursusmål
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
Sidst opdateret
21. juni, 2017