ID3005 Villkorsprogrammering 7,5 hp

Constraint Programming

Kursens tema är att modellera och lösa kombinatoriska (optimerings) problem med hjälp av villkorsprogrammering ("constraint  programming"). Villkorsprogrammering har pekats ut som ett strategiskt område inom datalogi av ACM. Kombinatoriska problem finns over­ alit, exempelvis att tilldela och schemalägga resurser, designa instruktioner för  processorer, samt optimera instruktionsschemaläggning vid kompilering. Den här kursen behandlar de grundläggande koncepten inom villkorsprogrammering, tillämpningar, utökningar, nuvaran­ de forskningstrender, samt dess relation till andra tekniker  for kombinatorisk optimering.

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Kurstillfällen/kursomgångar

VT19 för programstuderande

  • Perioder

    VT19 P4 (7,5 hp)

  • Anmälningskod

    61156

  • Kursen startar

    2019-03-18

  • Kursen slutar

    2019-06-04

  • Undervisningsspråk

    Engelska

  • Studielokalisering

    KTH Kista

  • Undervisningstid

    Dagtid

  • Undervisningsform

    Normal

  • Antal platser

    Ingen begränsning

  • Kursansvarig

    Christian Schulte <cschulte@kth.se>

Information för forskarstuderande om när kursen ges

Varje år, period 4 tillsammas med ID2204.

Lärandemål

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).

Kursens huvudsakliga innehåll

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öd­vä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 kopp­lingar till andra forskningsområden.

Behörighet

Litteratur

Examination

  • EXA1 - Examination, 7,5, betygsskala: P, F

Godkänd skriftlig tentamina,  godkända inlämningsuppgifter och godkänd tillämpning av nu­ varande forskning (till exempel: användning i en forskningsartikel, forskningsrapport, eller forskningsprojekt).

Kursen betygsatts med betygen P /F (godkänd eller underkänd).

Ges av

EECS/Programvaruteknik och datorsystem

Kontaktperson

Christian Schulte, cschulte@kth.se 087904264

Examinator

Christian Schulte <cschulte@kth.se>

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.