Heltalsprogrammering

• Define et “mixed integer” program, et heltalsprogram og et binært program i forhold til et lineært program.
• Opstille en heltalsprogrammering model med målfunktion, begrænsninger og variabeldefinition ud fra en simpel tekst.
• Definer en formulering og vis eksempler på anvendelser.
• Anvend bounds på et heltalsprogrammeringsproblem og vurder deres effektivitet.
• Definere en relaksering og beskrive eksempler på relaksering fra pensum, inklusiv LP relaksering og Lagrange relaksering.
• Anvend Lagrange relaxering på et simpelt IP problem.
• Beskrive konstruktionen af en branch-and-bound (B&B) algoritme for et standard IP problem.
• Beskriv betydningen af og indholdet af de centrale beviser indenfor heltalsprogrammering som angivet i kurset.
• Demonstrer hvordangyldige uligheder og snit generelt virker og specifikt i forbindelse med et heltalsprogrammeringsproblem. Definer Gomory cuts.
• Beskrive problemstillingerne ved udvidelsen fra uligheder og snit til en branch-and-cut (B&C) algoritme.
• 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).
• Opstille en dynamisk programmerings algoritme bestående af “princple 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.

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

Forelæsninger, øvelser og projektarbejde