book

Constraint Processing

by Rina Dechter

May 2003

Intermediate to advanced

480 pages

14h 1m

English

Morgan Kaufmann

Read now

Unlock full access

1.1 Basic Concepts and Examples1.2 Overview by Chapter1.3 Mathematical Background1.4 Bibliographical Notes1.5 Exercises

2.1 Constraint Networks and Constraint Satisfaction2.2 Numeric and Boolean Constraints2.3 Properties of Binary Constraint Networks2.4 Summary2.5 Bibliographical Notes2.6 Exercises
3.1 Why Propagate Constraints?3.2 Arc-Consistency3.3 Path-Consistency3.4 Higher Levels of i-Consistency3.5 Arc-Consistency for Nonbinary Constraints3.6 Constraint Propagation for Numeric and Boolean Constraints3.7 Trees, Bivalued Networks, and Horn Theories3.8 Summary3.9 Bibliographical Notes3.10 Exercises
4.1 Graph Concepts: Induced Width4.2 Directional Local Consistency4.3 Width versus Local Consistency4.4 Adaptive Consistency and Bucket Elimination4.5 Summary4.6 Bibliographical Notes4.7 Exercises
5.1 The State Space Search5.2 Backtracking5.3 Look-Ahead Strategies5.4 Satisfiability: Look-Ahead in Backtracking5.5 Summary5.6 Bibliographical Notes5.7 Exercises
6.1 Conflict Sets6.2 Backjumping Styles6.3 Complexity of Backjumping6.4 Learning Algorithms6.5 Look-Back Techniques for Satisfiability6.6 Integration and Comparison of Algorithms6.7 Summary6.8 Bibliographical Notes6.9 Exercises
7.1 Greedy Local Search7.2 Random Walk Strategies7.3 Hybrids of Local Search and Inference7.4 Summary7.5 Bibliographical Notes7.6 Exercises
8.1 Relational Consistency8.2 Directional Consistency Revisited8.3 Domain and Constraint Tightness8.4 Inference for Boolean Theories8.5 Row-Convex Constraints8.6 Linear Inequalities8.7 Summary8.8 Bibliographical Notes8.9 Exercises
9.1 Acyclic Networks9.2 Tree-Based Clustering9.3 ADAPTIVE-CONSISTENCY as Tree Decomposition9.4 Summary9.5 Bibliographical Notes9.6 Exercises
10.1 Specialized Cutset Schemes10.2 Hybrids: Conditioning First10.3 Hybrids: Inference First10.4 A Case Study of Combinatorial Circuits10.5 Summary10.6 Bibliographical Notes10.7 Exercises
11.1 The CSP Search Problem11.2 Constraint Languages11.3 Expressiveness of Constraint Languages11.4 Complexity of Constraint Languages11.5 Hybrid Tractability11.6 Summary11.7 Bibliographical Notes11.8 Exercises
12.1 Qualitative Networks12.2 Quantitative Temporal Networks12.3 Translations between Representations12.4 Summary12.5 Bibliographical Notes12.6 Exercises
13.1 Constraint Optimization and Cost Networks13.2 Branch-and-Bound Search13.3 Bucket Elimination for Optimization13.4 Mini-bucket Elimination13.5 Search with Mini-bucket Heuristics13.6 Empirical Demonstration13.7 Summary13.8 Bibliographical Notes13.9 Exercises
14.1 Bucket Elimination for Belief Assessment14.2 An Elimination Algorithm for mpe14.3 Complexity14.4 Hybrids of Elimination and Conditioning14.5 Summary14.6 Bibliographical Notes
15.1 Logic Programming15.2 Logic Programming as a Constraint Programming Language15.3 Syntax and Semantics of Constraint Logic Programming15.4 CLP over Finite Domain Constraints15.5 Issues and Notions Coming from CLP Use15.6 Summary15.7 Bibliographical Notes15.8 Exercises