Behörighetskrav

120 hp. Grundläggande koncept i algebra, kombinatorik, logik, graf- och mängdteori.

Kunna implementera enkla sökalgoritmer i valfritt gångbart programmeringsspråk.

Mål

För godkänt betyg ska studenten kunna

• beskriva och bevisa grundläggande koncept inom villkorsteknik.
• beskriva hur en allmän villkorslösare fungerar - arkitekturen och principerna.
• modellera kombinatoriska problem som ett villkorsprogram, med användning av grundvillkor från en villkorslösare.
• utforma (empiriskt) en fungerande heutistisk kontroll av sökningen som villkorsprogrammet utför.
• skriva och (empiriskt) jämföra olika villkorsprogram för samma problem.
• evaluera (empiriskt) konsekvensen för beräkningen av att introducera redundanta variabler.
• identifiera och ta bort (några av de) symmetrier i ett villkorsprogram för att snabba upp exekveringen.
• utöka en villkorslösare med ett ytterligare grundvillkor, utforma en filtreringsalgoritm för villkoret, och argumentera varför denna lösning är snabbare än den baserad på de ursprungliga grundvillkor.
• kortfattat beskriva alternativa teknologier för att modellera och lösa kombinatoriska problem, såsom heltalsprogrammering och lokal sökning.

Innehåll

Villkorsteknik (constraint technology) är ett samlingsnamn på vissa

metoder och verktyg för att lösa kombinatoriska problem. I dessa problem ska variabler tilldelas värden så att givna villkor uppfylls, alternativt att en given funktion av dessa variabler maximeras eller minimeras. Vanligtvis är antalet möjliga tilldelningar astronomiskt, så att naiv sökning även med snabba datorer inte löser problemet. Att effektivt lösa dessa problem är viktig i många praktiska tillämpningsområden: konfigurering, design, logistik, planering, schemaläggning, transporter, naturvetenskap, osv.

Kursen behandlar följande moment.

Villkorsteknikens grunder. Modellering med villkor.

Konsistens och spridning av villkor.

Globala villkor och deras spridningsalgoritmer.

Sökning: konstruktion och genomsökning av sökträdet, heuristiker.

Optimeringsproblem.

Avancerade lösningsmetoder: mängdvariabler, redundans och symmetri.

Alternativa teknologier: lokal sökning, heltalsprogrammering, boolsk satisfierbarhet, etc.

Implementering i ett villkorsspråk.

Undervisning

Föreläsningar, gästföreläsningar, laborationer, lektioner, övningar och ett obligatoriskt projekt.

Examination

Skriftlig examination vid kursens slut (4,5 hp).

Ett projekt under kursens gång (3 hp).