ID3005 Constraint Programming 7.5 credits
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 cycleThird cycle
Main field of study
Spring 18 P4 (7.5 credits)
Language of instruction
Form of study
Number of places
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 constraint 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 constraint programming relates to other methods (local search and integer programming).
• describe and apply current research trends in constraint programming in all areas mentioned 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 (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 genera tion, etc).
Research area overview: major conferences and journals. Current hot topics and connection to other research areas.
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).
ICT/Software and Computer system
Christian Schulte, email@example.com 087904264
Christian Schulte <firstname.lastname@example.org>
Course syllabus valid from: Spring 2011.