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.

• 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.

Branch & Bound, Snitplaner, Branch & Cut, Lagrange relaksering, dynamisk programmering. Eksempler på anvendelser: Projektplanlægning, rutelægning og produktionsplanlægning.

L. Wolsey: Integer Programming, Wiley. Kursusnoter

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/kursustilmelding.aspx