ID3005 Constraint Programming 7.5 credits

Villkorsprogrammering

  • Education cycle

    Third cycle
  • Main field of study

  • Grading scale

    P, F

Information for research students about course offerings

Every year, period 4 together with ID2204.

Intended learning outcomes

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.

Course main content

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.

Eligibility

Literature

Examination

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

Offered by

EECS/Software and Computer Systems

Contact

Christian Schulte, cschulte@kth.se 087904264

Examiner

Christian Schulte <cschulte@kth.se>

Version

Course syllabus valid from: Spring 2011.
Examination information valid from: Spring 2019.