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. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• 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. L. Wolsey: Integer Programming, Wiley. Kursusnoter. Bogen kan tilgås via DTUs bibliotek her: https:/​/​findit.dtu.dk/​en/​catalog/​60b61ffed9001d00f03caef8 21. juli, 2026