Matematisk optimering er en essentiel og kompleks del af data science. Som en del af optimering giver heltalsprogrammering mulighed for at udnytte ens data fuldt ud. I planlægning af f.eks. transport-, energi- eller produktionssystemer kan heltalsprogrammering give afgørende fordele. 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 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. L. Wolsey: Integer Programming, Wiley. Kursusnoter. Bogen kan tilgås via DTUs bibliotek her: https:/​/​findit.dtu.dk/​en/​catalog/​60b61ffed9001d00f03caef8 15. oktober, 2025