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

• Examination
• Assignments

Schedule 2012

The schedule is available in Daisy or here.

KTH Study Handbook

Entry for ID2204.

Contact

• Course responsible and examiner: Christian Schulte (cschulte@kth.se).