At give deltagerne en grundig indføring i problemformulering og løsningsmetodik for netværks- og heltalsprogrammeringsproblemer som disse opstår i bl.a. trafik-, transport-, investerings- og produktions-planlægning. Deltagerne bliver i stand til at formulere netværks- og heltalsprogrammeringsproblemer, 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 og bruge de centrale algoritmer indenfor de klassiske netværksproblemstillinger: mindst udspændende træ, korteste vej, projektplanlægning, maximum flow og minimum cost flow.
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. For netværksdelen betyder det korrekthed af de foreslået algoritmer.
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:
Lineær Programmering på grafer: Resume af relevant grafteori. Algoritmer til bestemmelse af korteste veje, maksimal strømning i netværk med kapacitetsbegrænsninger og strømning med minimal omkostning. Planlægningsnetværk: CPM/PERT. Heltalsprogrammering: Branch & Bound, Snitplaner, Branch & Cut, Lagrange relaksation. Eksempler på anvendelser: Projektplanlægning, rutelægning og produktionsplanlægning.
Litteratur:
L. Wolsey: Integer Programming, Wiley. Kursusnoter
