Enkeltfag Engelsk 5 ECTS

Heltalsprogrammering

Overordnede kursusmål

Matematisk optimering er en essentiel og kompleks del af data science. Heltalsprogrammering muliggør effektiv udnyttelse af data og ressourcer. I planlægning af f.eks. transport-, energi- eller produktionssystemer kan heltalsprogrammering give afgørende fordele gennem fokus på ressourceudnyttelse, omkostninger, robusthed og løsningskvalitet. Dette kursus giver de studerende en grundig introduktion til problemformulering og løsningsmetodik for heltalsprogrammeringsproblemer, som opstår i en lang række komplekse situationer. De studerende bliver i stand til både at formulere heltalsprogrammeringer og anvende dem til at etablere optimale løsninger for både simple og komplekse planlægnings- og beslutningsproblemer.

See course description in English

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 hvordan et branch-and-bound (B&B) træ for et standard IP problem opstilles og gennemløbes for derigennem at finde den optimale løsning.
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
Opstille en dynamisk programmeringsalgoritme for et simpelt optimeringsproblem herunder beskrive hvornår dynamisk programmering kan bruges og hvornår det ikke kan bruges.

Relaxation, dualitet, 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.