Heltalsprogrammering

• Definere og beskrive et “mixed integer”-program, et heltalsprogram og et binært program i forhold til et lineært program.
• Opstille en heltalsprogrammeringsmodel med målfunktion, begrænsninger og variabeldefinition ud fra en simpel tekst
• Definere en formulering og vise eksempler på anvendelser
• Anvende bounds på et heltalsprogrammeringsproblem og vurdere deres effektivitet
• Definere en relaksering og beskrive eksempler på relakseringer fra pensum, inklusiv LP-relaksering og Lagrange-relaksering
• Anvende Lagrange-relaksering på et simpelt IP problem
• Beskrive konstruktionen af en branch-and-bound (B&B) algoritme for et standard IP problem
• Beskrive betydningen af og indholdet i de centrale beviser inden for heltalsprogrammering, som angivet i kurset
• Demonstrere, hvordan gyldige uligheder og snit generelt fungerer, og specifikt i forbindelse med et heltalsprogrammeringsproblem
• Beskrive problemstillingerne ved udvidelsen fra uligheder og snit til en branch-and-cut (B&C) algoritme
• Beskrive brugen af B&B, B&C samt øvre og nedre grænser i forbindelse med implementering af effektive løsningsmetoder for simple IP-problemer (herunder især TSP)
• Opstille en dynamisk programmeringsalgoritme bestående af “principle of optimality”, “stage” og “state” for et simpelt problem

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

• 36 – 49 (tirs 13-17)

42101, Et indledende kursus i operationsanalyse er en nødvendig faglig forudsætning.

Forelæsninger, øvelser og projektarbejde.