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 villkorslösningsproblem.
• beskriva begreppet villkor, såsom det används i villkorsprogrammering (CP), samt hur en CP-lösare fungerar - genom att beskriva arkitekturen och de principer den baseras på.
• modellera kombinatoriska problem deklarativt med användning av grundvillkor från en CP-lösare.
• utforma (empiriskt) en fungerande sökheuristik som kan användas av en CP-lösare.
• skriva och (empiriskt) jämföra olika villkorsprogram (modell och sökning) för ett kombinatoriskt problem.
• utföra ändringar i en modell såsom att introducera redundanta variabler eller identifiera och ta bort symmetrier samt förklara vilka konsekvenser detta får för beräkningen.
• utöka en CP-lösare med ett ytterligare villkor och utvärdera om denna lösning är snabbare än en baserad på de ursprungliga villkoren.
• kortfattat beskriva alternativa kombinatoriska optimeringsteknologier och hybridteknologier.
• presentera och diskutera material relaterat till kursens innehåll muntligt och skriftligt med för utbildningsnivån lämplig färdighet.

Innehåll

Kursen behandlar modellering av optimeringsproblem översiktligt, fokus ligger på metoder för att lösa problemen.

Kombinatoriska optimerings- och villkorslösningsproblem. Villkor och globala villkor. Konsistens och propagering av villkor.

Modellering av kombinatoriska problem i termer av (globala villkor), reifikation, redundans i variabler och villkor, symmetrier i problem, modeller och instanser, mängdvariabler, mängdvillkor. Systematisk sökning: konstruktion och genomsökning av sökträdet, heuristiker, objektfunktioner för optimering. Villkorsbaserad stokastisk lokal sökning: konstruktion och genomsökning av sökrymden, heuristiker, meta-heuristiker. Villkorsbaserad schemaläggning. Alternativa teknologier: stokastisk lokal sökning, heltalsprogrammering, boolsk satisfierbarhet, hybridisering, etc. Tillämpningar och utökningar.

Undervisning

Föreläsningar, gästföreläsningar, obligatoriska uppgifter, handledning, lektioner, och ett obligatoriskt projekt.

Examination

Muntlig och skriftlig redovisning av uppgifter (2 hp) muntliga och skriftliga projektredovisningar (3 hp) skriftligt prov (5 hp) som i tillämpliga fall ingår i projektet.