Constraint Programming

Innehåll visas utifrån dina val

Om du inte hittar någon sida, schemahändelse eller nyhet på din kurswebb kan det bero på att du inte ser den kursomgången/gruppen inom kursen som innehållet tillhör.

Veta mer om din kurswebb

Din kurswebb är sidorna för en kurs du prenumererar på. Du väljer sedan vilka omgångar/grupper inom kursen du vill ha information från. Är du registrerad på en kursomgång sköts prenumeration och val av kursomgäng automatiskt åt dig. Vill du ändra något av detta gör du det under Mina inställningar.

När du är inloggad på din kurswebb ser du:
  • Kursöversikt, nyheter och schema med information som är filtrerat utifrån dina valda omgångar/grupper inom kursen
  • Allmänna sidor för hela kursen
  • Kurswikin som är sidor som alla, lärare och studenter, kan skapa och redigera
  • Sidor som hör till de omgångar/grupper inom kursen du valt eller som valts för dig

Log in to your course web

You are not logged in KTH, so we cannot customize the content.

The theme of the course is modeling and solving combinatorial (optimization) problems with constraint programming. Constraint programming has been identified by ACM as one of the strategic directions in computer science. Combinatorial problems are ubiquitous, a few examples are assigning and scheduling resources, designing processor instruction sets, and optimizing instruction ordering during compilation. The course covers the fundamental concepts underlying constraint programming, applications, extensions, and relation to other techniques employed in combinatorial optimization.

Aim

The overall aim of the course is to create understanding of the fundamental concepts underlying constraint programming; develop skills in modeling and solving combinatorial problems; develop skills in taking advantage of strong algorithmic techniques; create understanding of merits and limitations of constraint programming.

More specifically, after the course a student should be able to:

  • explain and apply basic modeling techniques for constraint problems, including the selection of variables, constraints, and optimization criteria.
  • describe and apply depth-first search and branch-and-bound search for solving constraint problems.
  • describe and define constraint propagation, search branching, and search tree exploration. Prove correctness, consistency, and completeness of propagators implementing constraints. Define and prove correctness of branching strategies. Describe optimizations of constraint propagation based on fixpoint reasoning.
  • describe advanced modeling techniques, analyze combinatorial problems for the applicability of these techniques, and apply and combine them. These techniques include: general symmetries, value and variable symmetries, symmetry breaking with constraints, symmetry breaking during search, domination constraints, redundant constraints, redundant modeling and channeling, using strong algorithmic techniques, and branching heuristics.
  • describe and apply Régin's algorithm for the distinct constraint as an example of strong constraint propagation. Explain algorithms for the element constraint, linear constraints, and disjunctive scheduling constraints. Implement a simple propagation algorithm.
  • describe the main strength and weaknesses of constraint programming and how constraint programming relates to other methods (local search and integer programming).

Syllabus

  • Modeling with constraint programming; basic solving methods: constraint propagation and search; typical techniques for modeling in different application areas (redundant constraints, symmetry elimination); refining models by strong algorithmic methods; heuristic search methods; application to hard real-size problems.
  • Basic principles underlying constraint programming; models for propagation and search and their essential properties; different levels of consistency; different constraint domains.
  • Strong algorithmic methods; Régin's distinct algorithm; edge-finding; integration (achieving required properties for propagation).
  • Relation to other techniques used in solving combinatorial problems (integer programming, local search); discussion of merits and weaknesses; hybrid approaches (column generation, etc).

Requirements

Approved written exam (TEN1; 4.5hp) and approved home assignments (LAB1; 3hp).

Teachers

No activity in the past month. Go to News feed to see older activity

Feedback News