Foundations of Constraint Satisfaction

PrefaceAcknowledgementsTable of contentsNotations and abbreviationsChapter 1 Introduction 1.1 What is a Constraint Satisfaction Problem? 1.1.1 Example 1 —The N-Queens Problem 1.1.2 Example 2 — The Car Sequencing Problem 1.2 Formal Definition of the CSP 1.2.1 Definitions of Domain and Labels 1.2.2 Definitions of Constraints 1.2.3 Definitions of Satisfiability 1.2.4 Formal Definition of Constraint Satisfaction Problems 1.2.5 Task in a CSP 1.2.6 Remarks on the Definition of CSPs 1.3 Constraint Representation and Binary CSPs 1.4 Graph-Related Concepts 1.5 Examples and Applications of CSPs 1.5.1 The N-Queens Problem 1.5.2 The Graph Colouring Problem 1.5.3 The Scene Labelling Problem 1.5.4 Temporal Reasoning 1.5.5 Resource Allocation in AI Planning and Scheduling 1.5.6 Graph Matching 1.5.7 Other Applications 1.6 Constraint Programming 1.7 Structure Of Subsequent Chapters 1.8 Bibliographical RemarksChapter 2 CSP Solving — An Overview 2.1 Introduction 31 2.1.1 Soundness and Completeness of Algorithms 2.1.2 Domain Specific vs. General Methods 2.2 Problem Reduction 2.2.1 Equivalence 2.2.2 Reduction of a Problem 2.2.3 Minimal Problems 2.3 Searching For Solution Tuples 2.3.1 Simple Backtracking 2.3.2 Search Space of CSPs 2.3.3 General Characteristics of CSP's Search Space 2.3.4 Combining Problem Reduction and Search 2.3.5 Choice Points in Searching 2.3.6 Backtrack-Free Search 2.4 Solution Synthesis 2.5 Characteristics of Individual CSPs 2.5.1 Number of Solutions Required 2.5.2 Problem Size 2.5.3 Types of Variables and Constraints 2.5.4 Structure of the Constraint Graph in Binary - Constraint-Problems 2.5.5 Tightness of a Problem 2.5.6 Quality of Solutions 2.5.7 Partial Solutions 2.6 Summary 51 2.7 Bibliographical RemarksChapter 3 Fundamental Concepts in the CSP 3.1 Introduction 3.2 Concepts Concerning Satisfiability and Consistency 3.2.1 Definition of Satisfiability 3.2.2 Definition of k-Consistency 3.2.3 Definition of Node- and Arc-Consistency 3.2.4 Definition of Path-Consistency 3.2.5 Refinement of PC 3.2.6 Directional Arc- and Path-Consistency 3.3 Relating Consistency to Satisfiability 3.4 (i,j)-Consistency 3.5 Redundancy of Constraints 3.6 More Graph-Related Concepts 3.7 Discussion and Summary 3.8 Bibliographical RemarksChapter 4 Problem Reduction 4.1 Introduction 4.2 Node and Arc-Consistency Achieving Algorithms 4.2.1 Achieving NC 4.2.2 A Naive Algorithm for Achieving AC 4.2.3 Improved AC Achievement Algorithms 4.2.4 AC-4, an Optimal Algorithm for Achieving AC 4.2.5 Achieving DAC 4.3 Path-Consistency Achievement Algorithms 4.3.1 Relations Composition 4.3.2 PC-1, a Naive PC Algorithm 4.3.3 PC-2, an Improvement Over PC-1 4.3.4 Further Improvement of PC Achievement Algorithms 4.3.5 GAC4: Problem Reduction for General CSPs 4.3.6 Achieving DPC 4.4 Post-Conditions of PC Algorithms 4.5 Algorithm for Achieving k-Consistency 4.6 Adaptive-Consistency 4.7 Parallel/Distributed Consistency Achievement 4.7.1 A connectionist Approach to AC Achievement 4.7.2 Extended Parallel Arc-Consistency 4.7.3 Intractability of Parallel Consistency 4.8 Summary 4.9 Bibliographical RemarksChapter 5 Basic Search Strategies for Solving CSPs 5.1 Introduction 5.2 General Search Strategies 5.2.1 Chronological Backtracking 5.2.2 Iterative Broadening 5.3 Lookahead Strategies 5.3.1 Forward Checking 5.3.2 The Directional AC-Lookahead Algorithm 5.3.3 The AC-Lookahead Algorithm 5.3.4 Remarks on Lookahead Algorithms 5.4 Gather-Information-while-Searching Strategies 5.4.1 Dependency Directed Backtracking 5.4.2 Learning Nogood Compound Labels Algorithms 5.4.3 Backchecking and Backmarking 5.5 Hybrid Algorithms and Truth Maintenance 5.6 Comparison of Algorithms 5.7 Summary 5.8 Bibliographical RemarksChapter 6 Search Orders in CSPs 6.1 Introduction 6.2 Ordering of Variables in Searching 6.2.1 The Minimal Width Ordering Heuristic 6.2.2 The Minimal Bandwidth Ordering Heuristic 6.2.3 The Fail First Principle 6.2.4 The Maximum Cardinality Ordering 6.2.5 Finding the Next Variable to Label 6.3 Ordering of Values in Searching 6.3.1 Rationale Behind Values Ordering 6.3.2 The Min-Conflict Heuristic and Informed Backtrack 6.3.3 Implementation of Informed-Backtrack 6.4 Ordering of Inferences in Searching 6.5 Summary 6.6 Bibliographical RemarksChapter 7 Exploitation of Problem-Specific Features 7.1 Introduction 7.2 Problem Decomposition 7.3 Recognition and Searching in k-Trees 7.3.1 "Easy Problems": CSPs which Constraint Graphs are Trees 7.3.2 Searching in Problems which Constraint Graphs are k-Trees 7.4 Problem Reduction by Removing Redundant Constraints 7.5 Cycle-Cutsets, Stable Sets and Pseudo_Tree_Search 7.5.1 The Cycle-Cutset Method 7.5.2 Stable Sets 7.5.3 Pseudo-Tree Search 7.6 The Tree-Clustering Method 7.6.1 Generation of Dual Problems 7.6.2 Addition and Removal of Redundant Constraints 7.6.3 Overview of the Tree-Clustering Method 7.6.4 Generating Chordal Primal Graphs 7.6.5 Finding Maximum Cliques 7.6.6 Forming Join-Trees 7.6.7 The Tree-Clustering Procedure 7.7 j-Width and Backtrack-Bounded Search 7.7.1 Definition of j-Width 7.7.2 Achieving Backtrack-Bounded Search 7.8 CSPs with Binary Numerical Constraints 7.8.1 Motivation 7.8.2 The AnalyseLongestPaths Algorithm 7.9 Summary 7.10 Bibliographical RemarksChapter 8 Stochastic Search Methods for CSPs 8.1 Introduction 8.2 Hill-Climbing 8.2.1 General Hill-Climbing Algorithms 8.2.2 The Heuristic Repair Method 8.2.3 A Gradient-Based Conflict Minimization Hill-Climbing Heuristic 8.3 Connectionist Approach 8.3.1 Overview of Problem Solving Using Connectionist Approaches 8.3.2 GENET, a Connectionist Approach to the CSP 8.3.3 Completeness of GENET 8.3.4 Performance of GENET 8.4 Summary 8.5 Bibliographical RemarksChapter 9 Solution synthesis 9.1 Introduction 9.2 Freuder's Solution Synthesis Algorithm 9.2.1 Constraints Propagation in Freuder's Algorithm 9.2.2 Algorithm Synthesis 9.2.3 Example of Running Freuder's Algorithm 9.2.4 Implementation of Freuder's Synthesis Algorithm 9.3 Seidel's Invasion Algorithm 9.3.1 Definitions and Data Structure 9.3.2 The Invasion Algorithm 9.3.3 Complexity of Invasion and Minimal Bandwidth Ordering 9.3.4 Example Illustrating the Invasion Algorithm 9.3.5 Implementation of the Invasion Algorithm 9.4 The Essex Solution Synthesis Algorithms 9.4.1 The AB Algorithm 9.4.2 Implementation of AB 9.4.3 Variations of AB 9.4.4 Example of Running AB 9.4.5 Example of Running AP 9.5 When to Synthesize Solutions 9.5.1 Expected Memory Requirement of AB 9.5.2 Problems Suitable for Solution Synthesis 9.5.3 Exploitation of Advanced Hardware 9.6 Concluding Remarks 9.7 Bibliographical RemarksChapter 10 Optimization in CSPs 10.1 Introduction 10.2 The Constraint Satisfaction Optimization Problem 10.2.1 Definitions and Motivation 10.2.2 Techniques for Tackling the CSOP 10.2.3 Solving CSOPs with Branch and Bound 10.2.4 Tackling CSOPs Using Genetic Algorithms 10.3 The Partial Constraint Satisfaction Problem 10.3.1 Motivation and Definition of the PCSP 10.3.2 Important Classes of PCSP and Relevant Techniques 10.4 Summary 10.5 Bibliographical RemarksProgramsBibliographyIndex