ID3005 Constraint Programming 7.5 credits

Villkorsprogrammering

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 con­ cepts underlying constraint programming, applications, extensions, current research topics, and relation to other techniques employed in combinatorial optimization.

  • Education cycle

    Third cycle
  • Main field of study

  • Grading scale

Course offerings

Spring 18 for programme students

  • Periods

    Spring 18 P4 (7.5 credits)

  • Application code

    61364

  • Start date

    19/03/2018

  • End date

    04/06/2018

  • Language of instruction

    English

  • Campus

    KTH Kista

  • Tutoring time

    Daytime

  • Form of study

    Normal

  • Number of places

    No limitation

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

ICT/Software and Computer system

Contact

Christian Schulte, cschulte@kth.se 087904264

Examiner

Christian Schulte <cschulte@kth.se>

Version

Course syllabus valid from: Spring 2011.