Foundations of Constraint Satisfaction discusses the foundations of constraint satisfaction and presents algorithms for solving constraint satisfaction problems (CSPs). Most of the algorithms described in this book are explained in pseudo code, and sometimes illustrated with Prolog codes (to illustrate how the algorithms could be implemented).

Comprised of 10 chapters, this volume begins by defining the standard CSP and the important concepts around it and presenting examples and applications of CSPs. The reader is then introduced to the main features of CSPs and CSP solving techniques (problem reduction, searching, and solution synthesis); some of the most important concepts related to CSP solving; and problem reduction algorithms. Subsequent chapters deal with basic control strategies of searching which are relevant to CSP solving; the significance of ordering the variables, values and compatibility checking in searching; specialized search techniques which gain their efficiency by exploiting problem-specific features; and stochastic search approaches (including hill climbing and connectionist approaches) for CSP solving. The book also considers how solutions can be synthesized rather than searched for before concluding with an analysis of optimization in CSPs.

This monograph can be used as a reference by artificial intelligence (AI) researchers or as a textbook by students on advanced AI courses, and should also help knowledge engineers apply existing techniques to solve CSPs or problems which embed CSPs.

Preface
Acknowledgements

Table of contents

Notations and abbreviations

Chapter 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 Remarks

Chapter 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 Remarks

Chapter 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 Remarks

Chapter 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 Remarks

Chapter 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 Remarks

Chapter 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 Remarks

Chapter 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-Bounde…