Edward Tsang. Foundations of Constraint Satisfaction

Monograph, London, 1996, 441 p.Many problems can be formulated as constraint satisfaction problems (CSP), although researchers untrained in the field sometimes fail to recognize them and therefore cannot use specialized techniques to solve them. In recent years, constraint satisfaction has come to be considered as a fundamental problem in many applications, such as timing reasoning, resource allocation, and scheduling. Its role in logic programming is also recognized. The importance of satisfying constraints is reflected in the abundance of publications made at conferences.The scattered and disorganized material in the field of constraint satisfaction, as well as the variety of terminology used in different parts of the literature, make this important topic more difficult to study than it needs to be. One of the goals of this book is to summarize the results of CSP research to date and to help newcomers to the field learn the issue more easily. The goal here is to organize and explain existing work in the field of CSP, as well as to provide pointers to cutting-edge research in the field. This book mainly focuses on algorithms for solving CSP.This volume can be used as a reference by artificial intelligence researchers or as a textbook for students in advanced artificial intelligence courses. It should also help knowledge engineers apply existing techniques to solve CSPs or problems in which CSPs are embedded. Most of the algorithms described in this book are explained in pseudocode and are sometimes illustrated with Prolog code (to illustrate how the algorithms can be implemented). Prolog was chosen because it allows the logic of algorithms to be shown more clearly than other languages. Here I have tried as much as possible to stick to pure Prolog and avoid the use of non-logical constructs such as statements and indentations.Figures.What is a constraint satisfaction problem?
Formal Definition of the CSP.
Constraint Representation and Binary CSPs.
Graph-related Concepts.
Examples and Applications of CSPs.
Constraint Representation and Binary CSPs.
Graph-related Concepts.
Examples and Applications of CSPs.
Constraint Programming.
Structure Of Subsequent Chapters.
Bibliographical Remarks.
CSP solving — An overviewProblem Reduction.
Searching For Solution Tuples.
Solution Synthesis.
Characteristics of Individual CSPs.
Solution Synthesis.
Characteristics of Individual CSPs.
Solution Synthesis.
Characteristics of Individual CSPs.
Solution Synthesis.
Characteristics of Individual CSPs.Bibliographical Remarks.
Fundamental concepts in the CSPConcepts Concerning Satisfiability and Consistency.
Relating Consistency to Satisfiability (i, j)-consistency.
Redundancy of Constraints.
More Graph-related Concepts Discussion and Summary Bibliographical Remarks.
Problem reductionNode and Arc-consistency Achieving Algorithms.
Path-consistency Achievement Algorithms.
Post-conditions of PC Algorithms.
Algorithm for Achieving k-consistency.
Adaptive-consistency.
Parallel/Distributed Consistency Achievement.Bibliographical Remarks.
Basic search strategies for solving CSPsGeneral Search Strategies.
Lookahead Strategies.
Gather-information-while-searching Strategies.
Hybrid Algorithms and Truth Maintenance.
Comparison of Algorithms.Bibliographical Remarks.
Search orders in CSPsOrdering of Variables in Searching.
Ordering of Values in Searching.
Ordering of Inferences in Searching.Bibliographical Remarks.
Exploitation of problem-specific featuresProblem Decomposition.
Recognition and Searching in K-trees.
Problem Reduction by Removing Redundant Constraints.
Cycle-cutsets, Stable Sets, and Pseudo Tree Search.
The Tree-clustering Method.
j-width and Backtrack-bounded Search.
CSPs with Binary Numerical Constraints.Bibliographical Remarks.
Stochastic search methods for CSPsHill-climbing.
Connectionist Approach.Bibliographical Remarks.
Solution synthesisFreuder’s Solution Synthesis Algorithm.
Seidel’s Invasion Algorithm.
The Essex Solution Synthesis Algorithms.
When to Synthesize Solutions.
Concluding Remarks Bibliographical Remarks.
Bibliographical Remarks.
Optimization in CSPsThe Constraint Satisfaction Optimization Problem.
The Partial Constraint Satisfaction Problem.Bibliographical Remarks.
Programs.

Index