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

STADS: 15015501

Niveau
Kandidatkursus

Undervisningsperiode
Kurset udbydes efter behov.

Ansvarlige undervisere
Marco Chiarandini, Lektor,
Tlf.: 6550 4031 Email: marco@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 16-18 IMADA semi 36-41,43-44,46,48-51
Fælles I Mandag 16-18 U17 47
Fælles I Onsdag 16-18 IMADA semi 36-41,44,51
Fælles I Onsdag 16-18 U145 43,47-50
Fælles I Onsdag 16-18 U21 46
Fælles I Torsdag 08-10 U143 36,50
Fælles I Torsdag 08-10 IMADA semi 37,39,41,43-44,49,51
Fælles I Torsdag 08-10 U145 38,40,47
Fælles I Torsdag 08-10 U21 46
Fælles I Fredag 08-10 U152 48
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:

  • Have kendskab til lineær og heltalsprogrammering
  • Kunne anvende algoritmer og data strukturer
  • Kunne vurdere kompleksitet af algoritmer, såvel med hensyn til køretid som med hensyn til pladsforbrug
  • Kunne programmere


Formål
Kurset har til formål at sætte den studerende i stand til at løse i praksis diskrete optimeringsproblemer, hvilket er vigtigt i forhold til at finde højeffektive løsninger til industrielle anvendelser som skedulering, logistik, energiplanlægning, sportsplanlægning, mm. Diskret Optimering er et spændende videnskabeligt felt der beskæftiger sig med problemer som er oftest meget svære at løse. Constraint Programmering (CP) og Lokal Søgning (LS) er to løsningsparadigmer til generelle formål for disse problemer. 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 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 de grundlæggende begreber, der er omfattet i forelæsningerne.

Kurset bygger oven på den viden, der er erhvervet i kurserne DM550, Introduktion til Programmering, og DM507, Algoritmer og datastrukturer. Referencer til koncepter fra DM554, Lineær og heltalsprogrammering, kan finde sted i kursusforløbet. Kurset giver et fagligt grundlag for at lave et speciale, hvor constraint programmering og heuristikker anvendes.

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 analysere fordele og ulemper ved forskellige algoritmer, specielt med hensyn til ressourceforbrug
  • 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 gennem en skriftlig rapport forskningsbaseret viden og diskutere professionelle og videnskabelige problemstillinger med fagfæller
  • Give ekspertviden om diskret optimering og løsning metoder fra fagets internationale forskningsfront


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

  • 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.
  • beskrive det udførte arbejde i et passende sprog, evt. med brug af pseudokode
Indhold
Kurset indeholder følgende faglige hovedområder:

  • Introduktion til Diskret optimering;
  • Modellering i constraint programmering med heltals og mængde variabler;
  • Local consistency begreb,
  • Globale betingelser og filtering algoritmer;
  • Søgning;
  • Symmetribrud;
  • Konstruktion heuristikker og grådige algoritmer;
  • Lokal søgning: modellering og algoritme;
  • Metaheuristikker (variabel søgning, tabu søgning, simuleret udkøldning, iterated lokal søgning, evolutionære algoritmer);
  • Stor skala nabolag;
  • Metoder til eksperimentel analyse af optimeringsalgoritmer;
  • Anvendelser: constraint satisfaction , satisfiability, omrejsende sælger, graffarvning, sportsplanlægning, skedulering, ruteplanlægning, 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: 40 timer, heraf:
 - Eksaminatorie: 20 timer
 - Laboratorieøvelser: 20 timer

Aktiviteter i studiefasen

Undervisningsform
Aktiviteter i studiefasen:

  • Anvendelse af den tilegnede viden i praktiske projekter
  • Læsning af tildelte videnskabelige artikler/bogkapitler
  • Praktiske eksperimenter med de i kurset introducerede metoder


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 2016 til 31. august 2021.