Matematisk optimering er en essentiel og kompleks del af data science. Som en del af optimering giver heltalsprogrammering mulighed for at få det fulde udbytte ud af ens data. I planlægning af f.eks. transport-, energi eller produktionssystemer kan heltalsprogrammering give afgørende fordele. Dette kursus giver deltagerne en grundig indtroduktion til problemformulering og løsningsmetodik for heltalsprogrammeringsproblemer som disse opstår i en lang række komplekse situationer. Deltagerne bliver i stand til såvel af formulere heltalsprogrammeringer som at anvende det til at etablere optimale løsninger for såvel simple som komplekse planlægnings- og beslutningsproblemer. En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:

• define et "mixed integer" program, et heltalsprogram og et binært program i forhold til et lineært program.
• gennemføre simpel identifikation af løsningsmetoder for et heltalsprogrammerings (IP) problem.
• opstille en heltalsprogrammering model med målfunktion, begrænsninger og variabeldefinition ud fra en simpel tekst.
• definere en relaksering og beskrive eksempler på relaksering fra pensum
• beskrive konstruktionen af en branch-and-bound (B&B) algoritme for et standard IP problem.
• gengive betydningen af og indholdet af de centrale beviser indenfor heltalsprogrammering som angivet i kurset.
• definere og beskrive brugen af gyldige uligheder og snit generelt og specifikt i forbindelse med et givet simpelt IP problem.
• 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.
• definere Lagrange relaxering for et heltalsprogram og beskrive brugen af Lagrange relaxering på et simpelt IP 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 20. juli, 2022