Att modellera med villkorsprogrammering: grundläggande lösningsmetoder (villkorspro pagering och sökning), tekniker for modellering (redundanta villkor, symmetrielimi nering), förfining av modeller med hjälp av starka algoritmiska metoder, heuristiska sökmetoder, tillämpning på problem av industristorlek.
Grundläggande principer för villkorsprogrammering: modeller för propagering och sök ning samt deras väsentliga egenskaper, olika nivåer av överrensstämmelse ("consisten cy"), olika villkorsdomäner.
Starka algoritmiska metoder: Regin's algoritm for distinct, edge-finding, integrering (nödvändiga egenskaper for propagering).
Förhållande till andra tekniker för att lösa kombinatoriska problem: heltalsprogrammering, lokalsökning; diskussion om förtjänster och begränsningar, hybrid-varianter (t.ex. co lumn generation).
Forskningsöversikt: framträdande konferenser och tidskrifter. Nuvarande trender och kopplingar till andra forskningsområden.
Kursens övergripande mål är att skapa en förståelse för de grundläggande koncepten bakom villkorsprogrammering; öva upp färdighet i att modellera och lösa kombinatoriska problem; öva upp färdighet i att kunna utnyttja starka algoritmiska tekniker; skapa en förståelse för förtjänster och begränsningar hos villkorsprogrammering.
Efter kursen skall studenten kunna:
• förklara och använda grundläggande modelleringstekniker for villkorsproblem vilket inkluderar val av variabler, villkor, och optimeringskriterier.
• beskriva och använda djupet-först sökning samt branch-and-boundsökning för att lösa kombinatoriska problem.
• beskriva och förklara villkorspropagering samt förgrening och utforskning inom sök ning. Bevisa korrekthet, överensstämmelse ("consistency"), och fullständighet för pro pagerare som implementerar villkor. Definiera och bevisa korrekthet for förgrenings strategier. Beskriva optimeringar av villkorspropagering baserat på fixpunkts resonemang.
• beskriva avancerade modelleringstekniker, analysera om dessa tekniker är applicerbara på givna kombinatoriska problem. Exempel på tekniker ar: generella symmetrier, varde och variabel-symmetrier, symmetrieliminering med villkor, symmetrieliminering un dersökning, domineringsvillkor, redundanta villkor, redundant modellering och kana lisering, att använda starka algoritmiska tekniker och förgreningsheuristiker.
• beskriva och använda Regin's algoritm för distinct villkoret som ett exempel på stark villkorspropagering. Förklara algoritmer for element villkoret, linjära villkor, och vill kor for disjunkt schemaläggning. Implementera en enkel propageringsalgoritm.
• förklara de huvudsakliga förtjänsterna och begränsningarna med villkorsprogramme ring samt hur villkorsprogrammering relaterar till andra metoder (lokalsökning och heltalsprogrammering).