English | Log ind

42114 Heltalsprogrammering

2024/2025

Kursusinformation
Integer Programming
Engelsk
5
Kandidat
Kurset udbydes som enkeltfag
E4A (tirs 13-17)
Kurset undervises med øvelser mellem 13 og 15 og forelæsninger derefter fra 15 til 17. Enkelte forelæsninger udgår til fordel for support til projektet.
Campus Lyngby
Forelæsninger, øvelser og projektarbejde
13-uger
E4A, F4A
Skriftlig eksamen og bedømmelse af rapport(er)
Kurset evalueres ved et gruppeprojekt og en skriftlig eksamen indeholdende multiple choice spørgsmål. For at deltage i den skriftllige eksamen skal man bestå en projektopgave. Projektet kan løses i grupper på op til fire studerende. I den skriftlige eksamen vil der være være spørgsmål til projektet. Der foretages en helhedsvurdering.
Skriftlig eksamen: 4 timer
Alle hjælpemidler - uden adgang til internettet :

Lukket net.

7-trins skala , ekstern censur
42101 , Et indledende kursus i operationsanalyse er en nødvendig faglig forudsætning.
42101 , Et indledende kursus i operationsanalyse er en nødvendig faglig forudsætning.
Jesper Larsen , Lyngby Campus, Bygning 358, Tlf. (+45) 4525 3385 , jesla@dtu.dk
David Pisinger , Lyngby Campus, Bygning 358, Tlf. (+45) 4525 4555 , dapi@dtu.dk
Richard Martin Lusby , Tlf. (+45) 4525 3084 , rmlu@dtu.dk
42 Institut for Teknologi, Ledelse og Økonomi
I studieplanlæggeren
Dette kursus giver den studerende en mulighed for at lave eller forberede et projekt som kan deltage i DTUs studenterkonference om bæredygtighed, klimateknologi og miljø (GRØN DYST). Se mere på http://www.groendyst.dtu.dk
Overordnede kursusmål
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.
Læringsmål
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.
  • 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.
Kursusindhold
Relaxation, duality, Branch & Bound, snitplaner, Branch & Cut, Lagrange relaksering, dynamisk programmering. Eksempler på anvendelser: Projektplanlægning, rutelægning og produktionsplanlægning.
Litteraturhenvisninger
L. Wolsey: Integer Programming, Wiley. Kursusnoter. Bogen kan tilgås via DTUs bibliotek her: https:/​/​findit.dtu.dk/​en/​catalog/​60b61ffed9001d00f03caef8
Sidst opdateret
02. maj, 2024