Behörighetskrav

120 hp. Grundläggande koncept i algebra, kombinatorik, logik, graf- och mängdteori. Kunna implementera enkla sökalgoritmer. Motsvarande delar av Baskurs i matematik, Algebra I, samt 10 hp i programmering.

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).
• beskriva 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ökheuristisk 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.
• evaluera (empiriskt) konsekvensen för beräkningen av att introducera redundanta variabler eller villkor i en modell.
• identifiera och ta bort (några) symmetrier i en modell för ett kombinatoriskt problem och därmed snabba upp exekveringen.
• 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

För kombinatoriska optimeringsproblem, är målet att tilldela värden för variabler i givna diskreta domäner så att givna villkor uppfylls och att en given funktion av dessa variabler maximeras eller minimeras. Vanligtvis är problemet NP-svårt, så att naiv sökning även med snabba datorer inte löser problemet. Att effektivt lösa dessa problem blir allt viktigare i många praktiska tillämpningsområden, såsom resurstilldelning, personalplanering, schemaläggning, transport logistik, konfigurering, design, naturvetenskap, ekonomi och så vidare.

Kursen behandlar

Kombinatoriska optimerings- och villkorslösningsproblem.

illkor 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, uppgifts- och projektbonus och tentamen 5 hp.