DM872: Matematisk Optimering i Praksis

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340032102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Forår
Niveau: Kandidat

STADS ID (UVA): N340032101
ECTS-point: 5

Godkendelsesdato: 27-09-2021


Varighed: 1 semester

Version: Arkiv

Indgangskrav

Kurset kan ikke følges af studerende, der: har bestået DM858, DM204.

Faglige forudsætninger

Studerende, der følger kurset, forventes at: 

  • Have kendskab til indholdet af kurset: DM545 / DM871: Lineær og heltalsprogrammering
  • Kunne programmere

Formål

Kurset fokus er på avancerede løsningsteknikker til matematiske optimeringsproblemer, der opstår fra konkrete anvendelser i skedulering og ruteplanlægning. Eksempler på anvendelser er: flow shop og jobshop skedulering i produktion, ressourcebegrænset aktivitetsplanlægning, bemanding og arbejdshold planlægning, tidsplanlægning og køretøj ruteplanlægning med tidsvinduer. Kurset sigter på at give teorien bag løsningsmetoderne og frem for alt praktisk erfaring med at implementere dem på numeriske instanser af disse optimeringsproblemer.

Anvendelser vil blive præcist formuleret og modelleret med hensyn til blandet heltal og lineær programmering (MILP) problemer. På grund af størrelsen af disse instanser fra disse problemer er grundlæggende løsningsteknikker for MILP-problemer utilstrækkelige, og avancerede løsningsteknikker nødvendige. Vi vil lære om Lagrangian relaxation, Dantzig Wolfe decomposition, søjle generering og Benders decomposition med hovedfokus på implementeringen af disse teknikker på baggrund af et software system til MILP problemer.

Kurset bygger oven på den viden, der er erhvervet i kurset "Lineær og Heltalsprogrammering", og giver et fagligt grundlag for at lave et master thesis projekt og andre både teoretiske og praktiske studie-aktiviteter så vel som at studere emnerne for andre valgfri kurser, der kan vælges i Datalogi, MatØk, Anvendt Matematik eller andre uddannelsen.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

  • Give kompetence til at planlægge og udføre videnskabelige projekter på højt fagligt niveau herunder styre arbejds- og udviklingssituationer, der er komplekse, uforudsigelige og forudsætter nye løsningsmodeller
  • Give færdigheder i at beskrive, analysere og løse avancerede datalogiske problemstillinger ved hjælp af de lærte modeller
  • Give færdigheder i at belyse fremsatte hypoteser på kvalificeret teoretisk baggrund og forholde sig kritisk til egne og andres forskningsresultater og videnskabelige modeller
  • Give færdigheder i at udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det
  • Give færdigheder i at formidle forskningsbaseret viden og diskutere professionelle og videnskabelige problemstillinger med både fagfæller og ikke-specialister
  • Give ekspertviden på et afgrænset fagområde, der er baseret på det højeste internationale forskningsfelt inden for det datalogiske og operationsanalyse fagområde 
  • Give viden om et udvalg af specialiserede modeller og metoder udviklet inden for datalogi og operationsanalyse baseret på højeste internationale forskning, herunder emner fra fagets forskningsfront

Målbeskrivelse

For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at: 

  • Genkende og beskrive problemer, der opstår i planlægning og routing, ved brug af formel notation.
  • Formulere en matematisk (lineær) model fra en given problembeskrivelse i ord.
  • Beskrive avancerede løsninger, baseret på blandet heltal og lineær programmering.
  • Implementere avancerede løsninger til MILP-problemer ved brug af computersoftware.
  • Analysere løsningsmetoderne med hensyn til beregningstid og løsningskvalitet.
  • Tænk innovativt ved at se muligheder for at anvende teoretisk viden i erhverv.

Indhold

Kurset indeholder følgende faglige hovedområder:

  • Dantzig-Wolfe decomposition og Benders decomposition
  • Søjle generering og Lagrangian relaxation
  • Bemanding og arbejdshold planlægning
  • Køretøj ruteplanlægning
  • Software systemer til løsning af MILP-problemer 

Litteratur

Se itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Forår

Udprøvninger

Obligatoriske opgaver i form af små projekter, der laves i løbet af kurset.

EKA

N340032102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset 

ECTS-point

5

Uddybende information

Alle obligatoriske opgaver, der forgår løbende, skal gennemføres.
Eksamensformen ved reeksamen kan være en anden end eksamensformen ved den ordinære eksamen.

Vejledende antal undervisningstimer

48 timer per semester

Undervisningsform

På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

  • Introfase (forelæsning, holdtimer) - 26 timer
  • træningsfase: 22 timer,  heraf 22 timer eksaminatorier

I introfasen introduceres og perspektiveres begreber, teorier og modeller. I træningsfasen træner de studerende færdigheder og trænger dybere ned i det stof.

Aktiviteter i studiefasen:

  • Læse forskningartikler
  • Løse hjemmeopgaver
  • Anvende det tilegnede viden i praktiske opgaver

Ansvarlig underviser

Navn E-mail Institut
Marco Chiarandini marco@imada.sdu.dk Algorithms

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Uddannelsesjura & Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil Uddannelse Semester Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.
Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.