Kombinatorisk optimering med villkorsprogrammering
Kursplan, Avancerad nivå, 1DL441
- Kod
- 1DL441
- Utbildningsnivå
- Avancerad nivå
- Huvudområde(n) med fördjupning
- Datavetenskap A1N, Teknik A1N
- Betygsskala
- Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
- Fastställd av
- Teknisk-naturvetenskapliga fakultetsnämnden, 13 februari 2018
- Ansvarig institution
- Institutionen för informationsteknologi
Behörighetskrav
120 hp inklusive Baskurs i matematik, Algebra I samt en fortsättningskurs i programmering eller annan kurskombination innehållande grundläggande koncept i algebra, kombinatorik, logik, graf- och mängdteori samt implementering av enkla sökalgoritmer.
Mål
Efter godkänd kurs ska studenten kunna
- definiera begreppet kombinatoriskt (optimerings- eller satisfierbarhets-) problem
- förklara begreppet villkor, såsom det används i ett villkorsbaserat modelleringsspråk
- modellera ett kombinatoriskt problem i ett villkorsbaserat lösningsteknik-oberoende modelleringsspråk
- jämföra (empiriskt) flera modeller, såsom att introducera redundans eller identifiera och ta bort symmetrier
- beskriva och jämföra lösningstekniker som kan användas av backends till ett villkorsbaserat modelleringsspråk, t.ex. villkorsprogrammering, lokal sökning, Boolesk satisfierbarhet (modulo teorier) och heltalsprogrammering
- välja lämpliga lösningstekniker för ett nytt kombinatoriskt problem och motivera valet
- presentera och diskutera material relaterat till kursens innehåll muntligt och skriftligt med en för utbildningsnivån lämplig färdighet
- beskriva hur en constraint programming (CP) lösare fungerar, genom att beskriva arkitekturen och de principer den baseras på
- utöka en CP-lösare med en propagator för ett nytt villkor, och utvärdera (empiriskt) om propagatorn är snabbare än en definition baserad på lösarens ursprungliga villkor
- utforma (empiriskt) en (problemspecifisk) sökstrategi som kan användas av en CP-lösare
- designa och (empiriskt) jämföra flera villkorsprogram (modell och sökning) för ett kombinatoriskt problem
Innehåll
Användningen av verktyg för att lösa ett kombinatorisk problem, genom att först modellera problemet i ett lösningsteknik-oberoende villkorsbaserat modelleringsspråk och sedan köra modellen i en befintlig lösare.
Villkorskonsistens; villkorspropagering; fixpoint propageringsalgoritmen.
Lösa genom systematisk sökning: konstruera och utforska ett sökträd; branching strategier; hantera en "objective function" för optimering.
Lösa genom (villkorsbaserad) stokastisk lokal sökning: konstruera och utforska en sökrymd; villkors-violation; variabel-violation; undersöka drag; söknings heuristiker; meta-heuristiker.
Undervisning
Föreläsningar, gästföreläsningar, obligatoriska uppgifter, handledning, lektioner, och ett obligatoriskt projekt.
Examination
Muntlig och skriftlig redovisning av uppgifter (del 1: 3 hp).
Muntlig och skriftlig redovisning av uppgifter (del 2: 5 hp).
Muntliga och skriftliga projektredovisningar (2 hp).
Övriga föreskrifter
Kursen kan ej tillgodoräknas i examen tillsammans med 1DL451, 1DL448 Modellering för kombinatorisk optimering eller 1DL449 Villkorsmodellering för kombinatorisk optimering.