Essentials of Constraint Programming (Fruhwirth, Abdennadher, 2003)

Copyright (c) 2013 John L. Jerz

Essentials of Constraint Programming (Fruhwirth, Abdennadher, 2003)

Review

From the reviews:

"The book distinguishes itself as a concise, formal introduction to the field of constraint programming. In general, concision and precision come in pairs in this book, and the authors should be congratulated for this. … the uniform style of this book makes it easier and easier to be read. Its structure is also well designed and concocts to create a fluid presentation … . Anybody looking for a formal, essential but never shallow introduction to the field should definitely consider this book." (Rosella Gennari, Journal of Logic, Language and Information, Vol. 14, 2005)

Product Description

The book is a short, concise and complete presentation of constraint programming and reasoning. The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and solve problems with uncertain, incomplete information and combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design and analysis. The theoretically well-founded presentation includes application examples from real life. It introduces the common classes of constraint programming languages and constraint systems in a uniform way. Constraint solving algorithms are specified and implemented in the constraint handling rules language (CHR).

This book is ideally suited as a textbook for graduate students and as a resource for researchers and practitioners. The Internet support includes teaching material, software, latest news and online use and examples of the CHR language.

v Programming with constraints makes it possible to model and specify problems with uncertain, incomplete information and to solve combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis.

p.1 Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it. Eugene C. Freuder, Inaugural issue of the Constraints Journal, 1997

p.1 The idea of constraint-based programming is to solve problems by simply stating constraints (conditions, properties) which must be satisfied by a solution of a problem... Constraints can be considered as pieces of partial information. Constraints describe properties of unknown objects and relationships between them... Constraints allow for a finite representation and efficient processing of possibly infinite relations.

p.2 The advantages of constraint logic programming are: declarative problem modeling on a solid mathematical basis, propagation of the effects of decisions using efficient algorithms, and search for optimal solutions.

p.24 In the so-called constraint-and-generate methodology, first the constraints are applied to reduce the search space (i.e., the number of possible solutions) and then (if needed) a solution is generated.

p.60 Search

Local-consistency methods [JLJ - from top of page, In this method, small fixed-size sub-problems of the initial problem are considered repeatedly until a fixpoint is reached. The sub-problems are simplified and new implied (redundant) constraints are computed (propagated) from them] must be combined with search to achieve satisfaction-completedness, i.e., global consistency. Search brings back exponential complexity to combinatorial and other NP-complete constraint problems, because dependencies between choices are not and cannot be fully taken care of. Search is also called branching because it will introduce branches in the search tree. Search is a case analysis, that is case splitting by introducing choices.

Usually, search is interleaved with constraint solving. A search step is performed, it adds a new constraint, that is simplified together with the existing constraints. This process is repeated until a solution is found.

p.101 Constraint-based software can be used profitably for reasoning with incomplete but also complete information and for solving combinatorial problems in decision support systems (expert systems, intelligent agents).

p.102 The flexibility of the constraint-based approach constitutes the main advantage over specialized tools which are likely to be harder to maintain, because they possibly cannot be adapted as easily to a change in the problem... In research, constraints become a more and more mainstream formalism... Everywhere where resources have to be managed and their use to be optimized, constraint technology is a potential solution, therefore its use has been wide spread in industry from the very beginning.

Enter supporting content here