Programming with Constraints: An Introduction

Rating:
Summary: This is the best book on the subject.
Review: So simple, straight forward, highly comprehensive but elegant bok on this subject is rarely available. Most topics covered in the book are readable with almost no effort. This is due to the authors' inherent capability of presentation. The foundation of the book rests on constraint simplification and optimization(chapter 2). Definitions are clear with adequate examples. Chapter 4 to 10 deal with Constraint Logic Programming. Here the authors focuss various important issues that are needed to researchers in this domain.Many applications in these chapters are highlighted to introduce the concepts. The last 2 chapters deal with constraint databases and concurrent constraint programming languages. Though it is a monograph readers of general interest in AI will find the chapters 1-4 useful and highly readable for knowing the state-of-the-art of this subject.

Rating:
Summary: Very good introduction
Review: This book is one of the few devoted to constraint programming, and does a good job of introducing the field to those interested. Optimization problems are finding use of constraint programming and there are a few commercial packages available that implement constraint programming technique in optimization. The book can be used as a textbook of an actual course, since there are many exercises included in it. The authors encourage the reader to use the CLP(R) package, which is freely available, to solve some of the practical exercises.

After a brief introduction to constraint programming, the authors introduce three types of constraints that exist in constraint programming, namely arithmetic, tree, and finite domain. They also introduce three operations involving constraints: satisfiability, simplification, and optimization. The authors spend most of the chapter on the question of satisfiability. Constraints are defined from the standpoint of mathematical logic, along with what it means for them to be satisfiable, and a discussion on modeling with arithmetic constraints and constraint satisfaction is given with an example from electric circuits. Tree constraints are then discussed with an example of a C-language binary tree used to motivate the discussion. Boolean constraints are then discussed, along with sequence constraints, which are shown to have an interesting application to DNA mapping and decoding. An application to artificial intelligence is given, and this one involves constraints that are not taken from mathematics. The authors

finish the chapter with a discussion of constraint solving using local propagation, a technique used in graph theory.

The authors discuss the simplification and optimization of constraints in the next chapter. They show when constraints are redundant, give rules for deciding when one constraint is equivalent to another, and show how using projection can allow the simplifying of a constraint with respect to the variables of interest. When projection cannot be done, they then show how to add variables to a constraint in order to achieve simplification. The (polynomial-time) Dantzig simplex algorithm is discussed for problems with linear real arithmetic constraints. Algorithms are discussed for deciding when two constraints are equivalent or when one implies the other.

In chapter 3, the authors discuss constraint problems for the case where the constraint domain is a finite set. The arc and node consistency, bounds propagation, and integer programming techniques, familiar from AI and operations research, are discussed in detail. The famous N-queens problem is introduced as motivation for the constraint satisfaction problem. The free-ware Prolog package ECLiPSe is introduced in the practical exercises. The authors give references to an interesting application of constraint satisfaction problems to planning gene-splicing experiments (the MOLGEN system).

The next part of the book concerns the constraint logic programming (CLP) paradigm wherein the authors define constraint logic programs and programming techniques. The reader familiar with logic programming (Prolog for example), will clearly see the influence of ideas from that area, such as rules, goals, rewriting, and derivations. An interesting and useful example of applying CLP to the modeling of options trading is given. Also, the authors show how to employ some of the more common data structures, such as lists and binary trees into CLP. In addition, they show how one can measure the efficiency of a CLP program, and how to improve it using various programming techniques to reduce the search space. The authors show how CLP can be implemented for both cases of infinite and finite domain constraints.

In the last part of the book the authors discuss other ways of viewing constraint logic programs, such as thinking it in terms of a database, called a constraint database. The discussion is very interesting, for the authors show how they are generalizations of the standard databases, and they show how the usual evaluation techniques in CLP, such as backtracking, must be generalized if one is to efficiently implement constraint databases. This "bottom-up" evaluation is compared with the "top-down"; approach usually employed. They show in great detail how constraint databases are a natural generalization of relational databases. They also show how CLP can be generalized to the case of concurrent constraint programming, where agents can execute concurrently and communicate via some global constraint in memory. In addition, they give a brief overview of how CLP can be implemented into the functional and imperative programming paradigms. They mention the use of various commercial packages for doing constraint programming, such as Mathematica, Maple, Macsyma, and ILOG SOLVER. Since the time of publication a very powerful commercial package, called ILOG OPL has appeared.

The applications of constraint programming are mushrooming, and I have found it to be a very powerful tool for example in network modeling and simulation, and in mathematical portfolio analysis, although sometimes one must be patient because of performance. The programming methodologies used are different than the usual ones, but I find them to be very effective for program transparency and economy of thought. Others have also apparently found constraint programming to be useful, for example the problem of protein structure prediction has recently made heavy use of constraint programming techniques. Other recent uses of CLP include a system for transport planning and scheduling for a large food industry, a system for a TV/radio company to plan and control the assignment of journalists and technicians to different emissions, and a system to develop work plans and schedules for train drivers and conductors, optimal planning of digital cordless communication systems, and nuclear fuel transportation and scheduling.