|
|
|
||
Last update: prof. RNDr. Roman Barták, Ph.D. (05.06.2017)
|
|
||
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)
The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency). Solving over-constrained problems is also discussed as well as some modeling techniques are covered. |
|
||
Last update: prof. RNDr. Roman Barták, Ph.D. (08.08.2022)
To successfully complete the course, the student is required to do the exam and to get credit. The credit is given for preparing constraint models during practical exercises. |
|
||
Last update: prof. RNDr. Roman Barták, Ph.D. (08.08.2022)
R. Dechter: Constraint Processing, Elsevier Science, 2003
K. Marriott, P.J. Stuckey: Programming with Constraints: An Introduction, The MIT Press, 1998
E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993
N. Zhou, H. Kjellerstrand, J. Fruhman: Constraint Solving and Planning with Picat, Springer, 2015 |
|
||
Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)
lecture |
|
||
Last update: prof. RNDr. Roman Barták, Ph.D. (06.10.2017)
The exam consists of a written preparation and an oral part. The requirements are given by the course syllabus. |
|
||
Last update: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)
1. Introduction: history and relation to other research areas, application areas, definition of a Constraint Satisfaction Problem and binary problems. 2. Local search techniques: hill climbing, min-conflicts, random walk, Tabu Search, GSAT, Genet. 3. Tree search techniques: backtracking, backjumping, dynamic backtracking, backmarking, limited discrepancy search, incomplete search. 4. Consistency techniques; node, arc, and path consistencies and algorithms to achieve them, general consistency notions. 5. Combining constraint propagation and search: forward checking, (partial/full) look ahead, variable and value ordering heuristics, backtrack-free search. 6. Optimization problems, branch and bound. Over-constrained problems and their models. 7. Global constraints. 8. Modelling problems and constraint programming in practice. |