DM841: Heuristikker og constraint programmering for diskret optimering (10 ECTS)

STADS: 15015501

Niveau
Kandidatkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.

Ansvarlige undervisere
Email: marco@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 08-10 IMADA Seminarrum 36,38,40
Fælles I Mandag 12-14 U49b 37
Fælles I Mandag 12-14 Spørg underviseren 37,37
Fælles I Tirsdag 14-16 IMADA Seminarrum 36,37,39,48,49,50,51
Fælles I Tirsdag 12-14 IMADA Seminarrum 41,41
Fælles I Onsdag 10-12 IMADA Seminarrum 37,40,43,44,45,46,47,48,49,50,51
Fælles I Torsdag 08-10 IMADA Seminarrum 38,39,41
Fælles I Fredag 08-10 IMADA Seminarrum 36,37,38,39,40,41,44,45,47,48,49,50,51
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra Introduktion til Programmering og Algoritmer og datastrukturer skal være kendt.

Kursusintroduktion
Diskret Optimering er et spændende videnskabeligt felt der blandt andet danner baggrund for højeffektiv skedulering, logistik, energiplanlægning, sportsplanlægning, mm. Problemer i Diskret Optimering er oftest meget svære og deres løsning er en udfordrende opgave. For at hjælpe i denne opgave er tre vigtige løsningsparadigmer til generelle formål blevet udviklet: Blandet Heltalsprogramming (BHP) , Constraint Programmering (CP) og Lokal Søgning (LS) . Dette kursus giver en introduktion til forskningsområdet om Diskret Optimering og fokuserer på to af dets løsningsparadigmer: CP og LS . Kurset er selvstændigt og det kræver ikke kendskab til BHP.Constraint Programmering er et programmeringssprogsparadigme, hvor variabler og betingelser mellem variabler udtrykkes i en deklarativ form. En løsning søges ved forsøgsvis at tildele en værdi valgt fra et gyldigt domæne til en variabel og derefter ved at filtrere i følge betingelserne givet ved domænerne for de øvrige variabler.
Generelle heuristikker og metaheuristikker er løst definerede regler for at finde nær-optimale løsninger. De er ofte inspireret af naturen. For eksempel er de lokale søgeteknikker baseret på princippet om trial and error, hvilket er en mulig måde, hvorpå mennesker intuitivt løser et problem. Succesen af specifikke heuristikker til at løse konkrete problemer på en tilfredsstillende måde afhænger af indsigt i strukturen af problemet og af muligheden for en effektiv implementering.

Man kan simpelthen ikke lære at takle de udfordringer man står over for i Diskret Optimering uden at forsøge at løse reelle problemer. Kurset sigter mod at give første hånds erfaring gennem programmeringsopgaver, der omfatter brug af værktøj, som illustrerer mange af de grundlæggende begreber, der er omfattet i forelæsningerne. 

Kompetencer
For at løse diskrete optimeringsproblemer, må den praktiserende have: problemløsningsfærdigheder, kendskab til generelle metoder, kendskab til konkrete tilgange til specifikke problemer, modelleringsfærdigheder, erfaring med implementering, analytiske kompetencer samt rapporteringsfærdigheder.

Forventet læringsudbytte
Ved afslutningen af kurset forventes den studerende at kunne:

  • modellere et problem der i natur minder om dem, der ses i kurset, inden for rammerne af constraint programmering og lokal søgning
  • argumentere vedrørende de forskellige modellerings valg med hensyn til teorien bag komponenterne af constraint programmering, herunder globale betingelser, propagators, søgning og forgreningsordninger.
  • udvikle en løsningsprototype ved hjælp af et constraint programmeringssystem
  • designe specialiserede versioner af generelle heuristikker: greedy og lokal søgning;
  • udvikle en løsningsprototype i et lokal søgningssystem
  • foretage en eksperimentel analyse, rapportere resultaterne og drage fornuftige konklusioner ud fra disse.
  • beskriver det udførte arbejde i et passende sprog, evt. med brug af pseudokode
Emneoversigt
Diskret optimering; problemformuleringer og modellering; generelle metoder; constraint programmering; constraint satisfaction model, søgning; propagation; local consistency, globale betingelser, symmetribrud, grådige algoritmer, træ-baserede søgeheuristikker; lokal søgning; stor skala nabolag; metaheuristikker (variabel søgning, tabu søgning, simuleret udkøldning, iterated lokal søgning, evolutionære algoritmer). Problemer: omrejsende sælger, graffarvning, sportsplanlægning, bil sekventering, ruteplanlægning, lager placering, skemalægning.

Litteratur
    Meddeles ved kursets start.


Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
  1. Obligatoriske opgaver, bedømmes efter 7-trinsskalaen, ekstern censur (10 ECTS). (15015502)

Evalueringen består af en række af opgaver (3-5) i løbet af kurset. Den endelige karakter er et vægtet gennemsnit af disse.
Reeksamen finder sted efter reglerne vedtaget af studienævnet. Den består af et enkelt projekt, hvis størrelse svarer til de opgaver, der er stillet i løbet af kurset.



Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 48 timer
Træningsfase: 20 timer, heraf:
 - Eksaminatorie: 20 timer

Aktiviteter i studiefasen Studiefase: 30 timer

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2014 til 31. august 2016.