Naučit základní používané techniky používané při úlohách splňování podmínek

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.

Pro úspěšné absolvování předmětu je potřeba získat zápočet a složit zkoušku. Zápočet je udělován za domácí úkoly (constraintové modely) zadávané v rámci cvičení.

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.

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

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

přednáška

lecture

Zkouška se skládá z písemné přípravy a ústní části. Požadavky odpovídají sylabu předmětu.

The exam consists of a written preparation and an oral part. The requirements are given by the course syllabus.

1. Úvod: historické souvislosti, vazba na další obory, aplikační oblasti, definice problému splňování omezujících podmínek, binarizace problémů.

2. Algoritmy lokálního prohledávání: metoda největšího stoupání, minimalizace konfliktů, náhodná procházka, Tabu seznam, GSAT, Genet.

3. Algoritmy prohledávání do hloubky: backtracking, backjumping, dynamický backtracking, backmarking, prohledávání s diskrepancemi, neúplné prohledávání.

4. Konzistenční techniky: vrcholová a hranová konzistence, konzistence po cestě a algoritmy pro jejich dosažení, obecné konzistenční pojmy.

5. Kombinace propagace podmínek a prohledávání: kontrola dopředu, (častěný/úplný) pohled dopředu, heuristiky pro uspořádání proměnných a hodnot, prohledávání bez navracení.

6. Optimalizační problémy, metody větví a mezí. Příliš omezené problémy a jejich modely.

7. Globální podmínky.

8. Modelování problémů a praktické realizace.

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.