FID3005 Constraint Programming 7.5 credits

Modeling with  constraint programming: typical techniques  for modeling in different ap­ plication 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  do­ roams.

Strong algorithmic methods: Regin's distinct  algorithm;  edge-finding; integration  (achiev­ing 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  genera­ tion, etc).

Research  area overview: major conferences and journals.  Current hot topics and connec­tion to other  research areas.

The overall aim of the course is to create understanding of the fundamental  concepts underly­ ing 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 con­straint problems.

• describe and define constraint propagation, search branching, and search tree explo­ ration.  Prove correctness, consistency, and completeness of propagators implementing constraints. Define and prove correctness of branching strategies.  Describe optimiza­ tions of constraint propagation based on fixpoint reasoning.

• describe  advanced modeling  techniques,  analyze combinatorial problems  for  the ap­ plicability  of these techniques,  and  apply  and combine  them.  These  techniques  in­ clude: general symmetries,  value and variable symmetries,  symmetry breaking with constraints, symmetry breaking during search, domination constraints, redundant con­ straints,  redundant  modeling and channeling, using strong algorithmic  techniques, and branching heuristics.

• describe and apply Regin's algorithm for the distinct constraint  as an example of strong constraint   propagation.    Explain  algorithms  for  the  element  constraint, linear  con­ straints,  and disjunctive scheduling  constraints.   Implement  a simple propagation  al­ gorithm.

• describe the main strength  and weaknesses of constraint  programming and how con­straint  programming relates to other methods (local search and integer programming).

• describe and apply current  research trends in constraint  programming in all areas men­tioned above.

If the course is discontinued, students may request to be examined during the following two academic years.

• EXA1 - Examination, 7.5 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Approved written  examination,  approved assignments, and approved application  of current research (in the form of using it for a research paper, report, or project, etc).

The course is graded with P/F (pass or fail).

Benoit Baudry

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.