ID2204 Constraint Programming 7.5 credits

• Educational level

  Second cycle

• Academic level (A-D)

  D

• Subject area

  Information Technology
  

• Grade scale

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

• Course homepage

• Course page on KTH Social

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

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, scientific articles, and course notes. 

Examination

• LAB1 - Laboratory Work, 3.0 credits, grade scale: P, F
• TEN1 - Examination, 4.5 credits, 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 plan valid from: Autumn 08.
Examination information valid from: Autumn 07.