Kombinatorisk optimering med villkorsprogrammering

Lärandemå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