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.
Show course information based on the chosen semester and course offering:
Offering and execution
No offering selected
Select the semester and course offering above to get information from the correct course syllabus and course offering.
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).
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).
No information inserted
Literature and preparations
Specific prerequisites *
Courses in basic computer science, discrete mathematics, algorithms and data structures. Basic object-oriented programming skills (for example: in Java or C++).
Knowledge corresponding to at least one of: SF1610 Discrete Mathematics, ID1015 Logic for Computer Science, ID2213 Logic Programming, ID1218 Applied Programming.
No information inserted
Hand outs, vetenskapliga artiklar och kurskompendium.
Examination and completion
Grading scale *
A, B, C, D, E, FX, F
Grading scale: P, F
Grading scale: A, B, C, D, E, FX, 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.
Other 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.
Opportunity to complete the requirements via supplementary examination
No information inserted
Opportunity to raise an approved grade via renewed examination