DM872: Matematisk Optimering i Praksis

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg udbydes efter følgende plan, når kurset udbydes:

Efterår: ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni)
Forår: ordinær eksamen (juni), første reeksamen (august) og 2. reeksamen i (januar)

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 linær- og heltalsprogrammering (eks. fra DM545 eller DM871),
kunne programmere (eks. fra DM574).

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.

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:

Branch and Cut
Lagrangian relaxation
Dantzig-Wolfe decomposition og Søjle generering
Branch and Price
Stochastic programmering
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

Efterår

Udprøvninger

Obligatoriske opgaver

EKA

N340032102

Censur

Intern prøve, to eller flere bedømmere

Bedømmelse

7-trinsskala

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Alle almindelige hjælpemidler tilladt

ECTS-point

Uddybende information

Eksamen består af to obligatoriske opgaver i form af små projekter, laves i løbet af kurset. De to opgaver vægter ligeligt ved karakterafgivelsen.

Vejledende antal undervisningstimer

48 timer per semester

Undervisningsform

Skemalagte undervisningstimer:

Antal undervisningstimer i alt: 48

Heraf:

Fællestimer i klasselokale/auditorium: 48

Fællestimerne vil være en blanding af klassiske forelæsninger og øvelsestimer. I forelæsningerne introduceres og perspektiveres begreber, teorier, modeller og algoritmer. I øvelsestimerne dykker de studerende længere ned i stoffet og træner deres færdigheder via øvelser.

Andre planlagte undervisningsaktiviteter:

Læse den tildelte litteratur
Løse hjemmeopgaver
Anvende den tilegnede viden i praktiske opgaver

Ansvarlig underviser

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

Yderligere undervisere

Navn	E-mail	Institut	By
Konstantin Pavlikov	kop@sam.sdu.dk	Institut for Virksomhedsledelse (IVL)

Skemaoplysninger

Odense

Vis fuldt skema (start E25)
Vis fuldt skema (start F26)

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos 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.