# Foundations of Constraint Satisfaction

## 1st Edition

### Computation in Cognitive Science

**Authors:**Edward Tsang

**eBook ISBN:**9781483220499

**Imprint:**Academic Press

**Published Date:**24th August 1993

**Page Count:**440

## Description

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.

## Table of Contents

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

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

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

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

Programs

Bibliography

Index

## Details

- No. of pages:
- 440

- Language:
- English

- Copyright:
- © Academic Press 1993

- Published:
- 24th August 1993

- Imprint:
- Academic Press

- eBook ISBN:
- 9781483220499