ID2204 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 teaches the fundamental concepts underlying constraint programming, applications, extensions, and relation to other techniques employed in combinatorial optimization.

  • Educational level

    Second cycle
  • Academic level (A-D)

    D
  • Subject area

    Information Technology
  • Grade scale

    A, B, C, D, E, FX, F

Course offerings

Spring 18 for programme students

Spring 19 for programme students

Intended learning outcomes

The theme of the course is modeling and solving combinatorial (optimization) problems with constraint programming. Constraintprogramming has been identified by ACM as one of the strategicdirections in computer science. Combinatorial problems areubiquitous, a few examples are assigning and schedulingresources, designing processor instruction sets, and optimizinginstruction ordering during compilation. The course covers thefundamental concepts underlying constraint programming,applications, extensions, and relation to other techniquesemployed in combinatorial optimization. 

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

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

Course main content

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

Eligibility

Courses in basic computer science, discrete mathematics, algorithms and data structures. Basic object-oriented programming skills (for example: in Java or C++). 

Recommended prerequisites

Knowledge corresponding to at least one of: SF1610 Discrete Mathematics, ID1015 Logic for Computer Science, ID2213 Logic Programming, ID1218 Applied Programming.

Literature

Hand outs, vetenskapliga artiklar och kurskompendium.

Examination

  • LAB1 - Laboratory Work, 3.0, grade scale: P, F
  • TEN1 - Examination, 4.5, grade scale: A, B, C, D, E, FX, F

Requirements for final grade

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

The home assignments are evaluated with the grades P/F (pass orfail). The course features four assignments which must be solved andsubmitted in time (you will have one week to solve all tasks onan assignment). Each assignment will feature 5 points ontasks. In order to pass the assignment part of the course youhave to reach 10 points on all assignments. If you submit an assignment in time, the points will serve asbonus points on the exam. That means that you can score at most20 bonus points for the exam. Note: the bonus points are validonly for this academic year. 

The tasks of the exam are worth 200 points. The grades for the entire course are defined by total pointsbeing the sum of the exam points and the bonus points you got onthe assignments. You need at least 100 total points to pass theexam. The written exam is evaluated with the grades A-F. 

The grades for the number of total points n are as follows:

n >= 180: A
180 > n >= 160: B 
160 > n >= 140: C
140 > n >= 120: D 
120 > n >= 100: E   
100 > n >= 80: Fx
80 > n       : F 

In case of the grade Fx, completing examination is possiblewithin one month after the original exam. In that case, thecourse responsible will on demand offer an extra home assignmentto be solved by the student within one week.

Offered by

ICT/Software and Computer system

Contact

Schulte, Christian

Examiner

Christian Schulte <cschulte@kth.se>

Version

Course syllabus valid from: Autumn 2008.
Examination information valid from: Autumn 2007.