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

• modellera ett kombinatoriskt problem i ett lösar-oberoende villkorsmodelleringsspråk
• jämföra och utvärdera modeller av kombinatoriska problem uttryckta i villkorsmodelleringsspråk
• beskriva och jämföra olika villkorslösningstekniker som kan användas av lösare till ett villkorsmodelleringsspråk, t.ex. villkorsprogrammering, lokal sökning, Boolesk satisfierbarhet och heltalsprogrammering
• välja en lämplig villkorslösningsteknik att prova för ett nytt kombinatoriskt problem och motivera valet
• designa och utvärdera olika modeller av kombinatoriska problem för olika villkorslösningstekniker.

Innehåll

Kursens fokus ligger på modellering av optimeringsproblem. Modellerna kan sedan användas för att lösa problemen med färdig lösare. Verktyg för att lösa svåra kombinatoriska optimeringsproblem genom att först modellera dem i ett lösaroberoende villkorsmodelleringsspråk för att sedan lösa dem med hjälp av en färdig lösare. Kombinatoriska (satisfierbarhets- eller optimerings-) problem, villkorsmodelleingsspråk, huvuddrag hos olika villkorslösningstekniker, heuristiker och "good practice" i modellering och lösning av kombinatoriska problem, exempel på tillämpningar av kombinatorisk problemlösning.

Undervisning

Föreläsningar, lektioner och handledning.

Examination

Muntlig och skriftlig redovisning av uppgifter.