Constraint Processing

Constraint Processing

by Rina Dechter
Released May 2003
Publisher(s): Morgan Kaufmann
ISBN: 9780080502953

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Constraint satisfaction is a simple but powerful tool. Constraints identify the impossible and reduce the realm of possibilities to effectively focus on the possible, allowing for a natural declarative formulation of what must be satisfied, without expressing how. The field of constraint reasoning has matured over the last three decades with contributions from a diverse community of researchers in artificial intelligence, databases and programming languages, operations research, management science, and applied mathematics. Today, constraint problems are used to model cognitive tasks in vision, language comprehension, default reasoning, diagnosis, scheduling, temporal and spatial reasoning. In Constraint Processing, Rina Dechter, synthesizes these contributions, along with her own significant work, to provide the first comprehensive examination of the theory that underlies constraint processing algorithms. Throughout, she focuses on fundamental tools and principles, emphasizing the representation and analysis of algorithms.
  • Examines the basic practical aspects of each topic and then tackles more advanced issues, including current research challenges
  • Builds the reader's understanding with definitions, examples, theory, algorithms and complexity analysis
  • Synthesizes three decades of researchers work on constraint processing in AI, databases and programming languages, operations research, management science, and applied mathematics

Table of contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. AUTHOR BIOGRAPHY
  5. Copyright
  6. Foreword
  7. Dedication
  8. Preface
  9. Chapter 1: Introduction
    1. 1.1 Basic Concepts and Examples
    2. 1.2 Overview by Chapter
    3. 1.3 Mathematical Background
    4. 1.4 Bibliographical Notes
    5. 1.5 Exercises
  10. Part I: Basics of Constraint Processing
    1. Chapter 2: Constraint Networks
      1. 2.1 Constraint Networks and Constraint Satisfaction
      2. 2.2 Numeric and Boolean Constraints
      3. 2.3 Properties of Binary Constraint Networks
      4. 2.4 Summary
      5. 2.5 Bibliographical Notes
      6. 2.6 Exercises
    2. Chapter 3: Consistency-Enforcing and Constraint Propagation
      1. 3.1 Why Propagate Constraints?
      2. 3.2 Arc-Consistency
      3. 3.3 Path-Consistency
      4. 3.4 Higher Levels of i-Consistency
      5. 3.5 Arc-Consistency for Nonbinary Constraints
      6. 3.6 Constraint Propagation for Numeric and Boolean Constraints
      7. 3.7 Trees, Bivalued Networks, and Horn Theories
      8. 3.8 Summary
      9. 3.9 Bibliographical Notes
      10. 3.10 Exercises
    3. Chapter 4: Directional Consistency
      1. 4.1 Graph Concepts: Induced Width
      2. 4.2 Directional Local Consistency
      3. 4.3 Width versus Local Consistency
      4. 4.4 Adaptive Consistency and Bucket Elimination
      5. 4.5 Summary
      6. 4.6 Bibliographical Notes
      7. 4.7 Exercises
    4. Chapter 5: General Search Strategies: Look-Ahead
      1. 5.1 The State Space Search
      2. 5.2 Backtracking
      3. 5.3 Look-Ahead Strategies
      4. 5.4 Satisfiability: Look-Ahead in Backtracking
      5. 5.5 Summary
      6. 5.6 Bibliographical Notes
      7. 5.7 Exercises
    5. Chapter 6: General Search Strategies: Look-Back
      1. 6.1 Conflict Sets
      2. 6.2 Backjumping Styles
      3. 6.3 Complexity of Backjumping
      4. 6.4 Learning Algorithms
      5. 6.5 Look-Back Techniques for Satisfiability
      6. 6.6 Integration and Comparison of Algorithms
      7. 6.7 Summary
      8. 6.8 Bibliographical Notes
      9. 6.9 Exercises
    6. Chapter 7: Stochastic Greedy Local Search
      1. 7.1 Greedy Local Search
      2. 7.2 Random Walk Strategies
      3. 7.3 Hybrids of Local Search and Inference
      4. 7.4 Summary
      5. 7.5 Bibliographical Notes
      6. 7.6 Exercises
  11. Part II: Advanced Methods
    1. Chapter 8: Advanced Consistency Methods
      1. 8.1 Relational Consistency
      2. 8.2 Directional Consistency Revisited
      3. 8.3 Domain and Constraint Tightness
      4. 8.4 Inference for Boolean Theories
      5. 8.5 Row-Convex Constraints
      6. 8.6 Linear Inequalities
      7. 8.7 Summary
      8. 8.8 Bibliographical Notes
      9. 8.9 Exercises
    2. Chapter 9: Tree Decomposition Methods
      1. 9.1 Acyclic Networks
      2. 9.2 Tree-Based Clustering
      3. 9.3 ADAPTIVE-CONSISTENCY as Tree Decomposition
      4. 9.4 Summary
      5. 9.5 Bibliographical Notes
      6. 9.6 Exercises
    3. Chapter 10: Hybrids of Search and Inference: Time-Space Trade-Offs
      1. 10.1 Specialized Cutset Schemes
      2. 10.2 Hybrids: Conditioning First
      3. 10.3 Hybrids: Inference First
      4. 10.4 A Case Study of Combinatorial Circuits
      5. 10.5 Summary
      6. 10.6 Bibliographical Notes
      7. 10.7 Exercises
    4. Chapter 11: Tractable Constraint Languages
      1. 11.1 The CSP Search Problem
      2. 11.2 Constraint Languages
      3. 11.3 Expressiveness of Constraint Languages
      4. 11.4 Complexity of Constraint Languages
      5. 11.5 Hybrid Tractability
      6. 11.6 Summary
      7. 11.7 Bibliographical Notes
      8. 11.8 Exercises
    5. Chapter 12: Temporal Constraint Networks
      1. 12.1 Qualitative Networks
      2. 12.2 Quantitative Temporal Networks
      3. 12.3 Translations between Representations
      4. 12.4 Summary
      5. 12.5 Bibliographical Notes
      6. 12.6 Exercises
    6. Chapter 13: Constraint Optimization
      1. 13.1 Constraint Optimization and Cost Networks
      2. 13.2 Branch-and-Bound Search
      3. 13.3 Bucket Elimination for Optimization
      4. 13.4 Mini-bucket Elimination
      5. 13.5 Search with Mini-bucket Heuristics
      6. 13.6 Empirical Demonstration
      7. 13.7 Summary
      8. 13.8 Bibliographical Notes
      9. 13.9 Exercises
    7. Chapter 14: Probabilistic Networks
      1. 14.1 Bucket Elimination for Belief Assessment
      2. 14.2 An Elimination Algorithm for mpe
      3. 14.3 Complexity
      4. 14.4 Hybrids of Elimination and Conditioning
      5. 14.5 Summary
      6. 14.6 Bibliographical Notes
    8. Chapter 15: Constraint Logic Programming
      1. 15.1 Logic Programming
      2. 15.2 Logic Programming as a Constraint Programming Language
      3. 15.3 Syntax and Semantics of Constraint Logic Programming
      4. 15.4 CLP over Finite Domain Constraints
      5. 15.5 Issues and Notions Coming from CLP Use
      6. 15.6 Summary
      7. 15.7 Bibliographical Notes
      8. 15.8 Exercises
  12. Bibliography
  13. Index

Product information

  • Title: Constraint Processing
  • Author(s): Rina Dechter
  • Release date: May 2003
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080502953