The concept of constraint processing, as addressed by this book, includes global constraints (three papers), search and heuristics (four papers), language and implementation issues (two papers), and modeling (three papers). A remarkable editing job has constrained paper lengths to an average of 15 pages. The papers are well written, and this should help the reader establish detailed connections among them (in the absence of an editorial overview).

The global constraints receiving attention (first section) are “all-different,” “global cardinality,” “lexicographical order,” “among,” “common,” and “disjoint.” The papers seek to reach beyond traditional finite variable domains by, first, generalizing to set, multiset, and tuple variables within the context of the all-different constraint, and capturing global cardinality via generalization; second, providing rigorous development backed by rich examples on lexicographical variables in a solution context of an incremental, concurrent logic solution method featuring the prime author’s constraint handling rules language (CHR); and, third, introducing set variables arising in tractable and intractable cases of among, common, and disjoint constraints (relations among several constraints are mentioned, and resource problems are referenced for motivation). Every paper here presents algorithms or rule sets, and explores their theoretical properties. Applications, for example in design theory and resource problems, establish research practicality. Future study is suggested almost invariably, sometimes at length.

Leading off the coverage of search and heuristics is a paper on graph coloring. Partitioning the problem domain is given early justification, and several theorems, based on one author’s previous work, cover algorithm correctness and complexity; no implementations or experiments are presented, but illuminating proofs and associated details may compensate for this. A specific partitioning approach, including the graph k-coloring problem and “non-dense instances of randomly generated CSPs,” then undergoes theoretical analysis, followed by experimental evaluations assessing “practical merits” in terms of number of nodes visited and runtime. Comparisons with forward checking (FC) emerge favorably for coloring, but less successfully for randomly generated problems. The next paper seeks means to predict the effectiveness of combinations of heuristics using factor analysis, which in the author’s earlier work translates into roles for “build up of contention” and “look-ahead-induced failure.” The study is primarily empirical, and comparisons involve several acknowledged combinations. Future research potentially overlaps with that proposed elsewhere in the book. The section’s final paper formalizes the complexity assessment of solution combinations by showing, for two specific algorithms (or, more precisely, for a given algorithm and any other meeting a specific criterion), that the combination reduces time complexity.

The CHR language reappears at the start of the next section, for language considerations. First, CHR is implemented over a host language, for example Java, Prolog, Haskell, or constraint logic programming (CLP), so that a postulated type system is parameterized by that of the host language. Theory evolves around general issues and specifically CLP, which includes type-checking software (TCLP). Consistency of the type system with regard to the operational semantics of CHR and CHR + CLP becomes the proof target. A dozen examples, including TCLP, bolster claims for practical use. The next, more descriptive paper’s topics are reflected in the chapter title’s references to (variable) views and (range) iterators. The discussion here revolves around making constraint implementations generic, reusing them with different constraints (by virtue of views), and decoupling propagators from variables via views and iterators. Examples and underlying implementation techniques, for example parametric polymorphism, lead to future work projections along similar lines, but also with richer variable views.

The final section includes three papers. The first, on stochastic constraint programs (CPs), addresses stochastic versions of template design, warehouse location, and news vendor problems. Decomposition into a master problem and slave subproblems, and restricting (problem) stochastic portions to a first stage, simplifies a scenario-based approach, and permits solutions consisting of constraint problem-linear programming (CP-LP) hybrids. Computational experiments present the authors’ main scheme as a winner over monolithic and related decomposition solutions. The second paper discusses weak symmetries, which appear in practice in such cases as constraint satisfaction programming (CSP) in the presence of objective functions and problems with soft constraints. Weak symmetries are defined in terms of weak decomposition. The author uses magic square problems to illustrate basics, as well as the prime theorem on breaking weak symmetries without losing solutions. A relaxed version of mounting components on personal computer (PC) boards shows the author’s heuristic approach is better than several standard heuristic approaches. The third paper seeks satisfiable problem generation, so that solution failure can be attributed to the solution method and not to the problem’s character. Online problem generation is deemed desirable for a desired CSP benchmarking capability.

The book amply demonstrates active CSP research. The maturity and balance of theory and practice are clearly communicated. Follow-up papers can be expected, and should generate appreciation where due.