-consistency, as well as, the relaxation to
bounds consistency. This is then applied to constraint propagation for
numeric and Boolean constraints.
Constraint Processing by Rina Dechter, Morgan Kaufmann Publishers, 2003, hard cover: ISBN 1-55860-890-7, xx + 481 pages.
``Constraint Processing'' provides a comprehensive treatment of the theory of Constraint Satisfaction Problems (CSP). Constraint processing has made important contributions to the area of Artificial Intelligence. It has also contributed to other areas such as programming languages, operations research and optimization, databases and applied mathematics. The book starts from the very basics of constraint satisfaction to the algorithms, inference and search techniques used in constraint processing. The focus is on a rigorous development of the fundamentals and principles of constraint satisfaction while at the same time being written in a readable textbook style.
The book consists of fifteen chapters divided into two main parts. Chapter 1 is an introduction. The first part from chapters 2 to 7 covers the basics of constraint processing. The second part from chapters 8 to 15 covers more advanced material.
In the first part, chapter 2 gives examples of constraint problems followed
by the basic definitions of constraint networks and their properties.
Chapter 3 develops the basic algorithms for constraint propagation.
It starts with the arc consistency algorithm, followed by
path consistency and -consistency, as well as, the relaxation to
bounds consistency. This is then applied to constraint propagation for
numeric and Boolean constraints.
Chapter 4 investigates properties which allow for backtrack-free search leading to directional and adaptive consistency. The next important ingredient is backtracking search in Chapter 5. Enhancements to backtracking search using various look-ahead strategies are developed and heuristics for determining value and variable ordering search strategies are covered.
Chapter 6 improves naive backtracking using look-back schemes for backjumping and learning. Backjumping is also integrated with look-ahead. Chapter 6 also introduces the use of random problems for studying algorithms and the phase transition phenomena encountered when solving hard problems. Chapter 7 completes the basic section with stochastic greedy local search as a complement to backtracking search. It discusses greedy and random walk strategies for local search and then integrates inference and local search.
In the second part of the book, chapter 8 first extends consistency notions developed in the first part, which are mainly on binary constraint networks, to the general non-binary case using relational consistency. This is then applied to domain tightness and constraint tightness to show when local consistency is also globally consistent. The rest of the chapter develops constraint inference for special classes of constraints, namely, row convex, Boolean and and linear arithmetic constraints.
Chapter 9 covers acyclic networks for non-binary constraints and tree decomposition methods. Chapter 10 revisits hybrid algorithms using search and inference. This chapter expands on the time-space trade-offs when combining structural properties of the constraint graph with search. Chapter 13 deals with solving optimization problems, first using branch-and-bound search and then the bucket and mini-bucket elimination which is a dynamic programming approach to optimization.
There are two chapters devoted to special kinds of constraint networks. Chapter 12 deals with temporal constraint networks which arise from temporal reasoning. Chapter 14 shows how the techniques developed such as bucket elimination and the cycle cutset method can be used in the context of probabilistic/bayesian networks. Finally, there are two contributed chapters. Chapter 11 by David Cohen and Peter Jeavons presents the theory of tractable constraint languages. Chapter 15 by Francesca Rossi describes the Constraint Logic Programming (CLP) scheme and its programming paradigm which integrates constraint processing into logic programming.
Throughout much of the book, constraint processing is applied to Boolean problems. Thus constraint processing for Boolean problems serves as a running example for the specialisation of the techniques discussed in the book. For example, the unit propagation algorithm is a special case of relational arc consistency for Boolean constraint propagation. Chapter 5 shows how using unit propagation with backtracking search defines the well known DPLL procedure for Boolean satisfiability. Chapter 6 adds learning to the SAT solver. Directional resolution is developed by specializing directional arc consistency in Chapter 8.
This is the first book with a rigorous treatment of the theory and algorithms for Constraint Satisfaction Problems. While it is not encyclopedic, it gives a broad coverage while covering the major CSP results. Algorithms are given an integrated treatment in a precise but understandable fashion. This is due in part to the systematic use of high level operations using constraint composition and projection in the algorithms and the presentation of algorithms as constraint inference. The time complexities of algorithms are covered. As mentioned, there is an emphasis on Boolean problems which is the consistent link across chapters. The author has presented experimental results in some of the more advanced material which is useful to understand practical performance and trade-offs of the various algorithms.
This book is on the theory of constraint processing. It is not about how to model problems, implementation of constraint solvers, heuristic for constraint problems (there is a small treatment in the book), how to solve combinatorial problems, etc.
To place the book in context, it is useful to compare it with two other books on constraints also published in 2003: (i) Thom Frühwirth and Slim Abdennadher, Essentials of Constraint Programming, Springer; and (ii) Krzysztof R. Apt, Principles of Constraint Programming, Cambridge. The approach of the first book is from a programming language perspective, namely, CLP. It also develops Constraint Handling Rules (CHR) as a programming language for writing constraint solvers. The second book covers both the constraint processing techniques in CSP as well as constraint programming. Like the first book the approach is also more rule based. The (present) book differs from the above two in its focus on the theory and algorithms for CSP. Although it has a chapter on CLP, this mainly serves as an introduction and linkage to constraint programming.
To summarize, this book distills well over three decades worth of development in CSP and constraint processing in a single textbook. I wholeheartedly recommend it to students, researchers and practitioners in artificial intelligence, constraint programming and operations research who want to know more about the theory of constraint processing.
ROLAND H.C. YAP
National University of Singapore, Singapore