Programming with Constraints: An Introduction

by Kim Marriott, Peter J Stuckey, Peter J. Stuckey, et al.

The job of the constraint programmer is to use mathematical constraints to model real world constraints and objects. In this book, Kim Marriott and Peter Stuckey provide the first comprehensive introduction to the discipline of constraint programming and, in particular, constraint logic programming. The book covers the necessary background material from artificial intelligence, logic programming, operations research, and mathematical programming...

• Format: Hardcover
• Language: English
• ISBN: 0262133415
• ISBN13: 9780262133418
• Release Date: March 1998
• Publisher: Mit Press
• Length: 488 Pages
• Weight: 2.95 lbs.
• Dimensions: 1.3" x 8.3" x 10.3"
• Age Range: 18 years and up
• Grade Range: Postsecondary and higher

Customer Reviews

Very good introduction

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 prog

This is the best book on the subject.

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.