You wait forever for one to come along, and then two come along at once. In this case, there has been a large gap in the market for a theoretical introduction to constraint programming ever since Edward Tsang's Foundations of Constraint Satisfaction (1993) went out of print. Therefore, we are very pleased to see two books written by two of the leading researchers in this field come along to fill the gap. Constraint programming is a very active research area within AI. It is a highly successful technology for solving a wide range of combinatorial problems, including scheduling, rostering, assignment, routing, and design. A number of companies, like ILOG, Dash Optimization, and Parc Technologies, market model building and constraint programming toolkits, which are used by companies as diverse as Amazon.com, Constraint programming is a declarative style of modeling combinatorial problems in which the user identifies the decision variables, their possible domain of values, and specifies constraints over the allowed values (for example, no two of these variables can take the same value). Sophisticated but general purpose AI search techniques like constraint propagation (to prune irrelevant parts of the search tree) and dependency directed backtracking can then be used to find solutions. Given the many advances made in constraint programming over the last decade, a new text would have been needed even if Edward Tsang's book had remained in print. These two new texts are written by two of the leading researchers in this field. Principles of Constraint Programming by Krzysztof Apt contains chapters that cover topics like local consistency, constraint propagation, linear equations, interval reasoning, and search. Constraint Processing by Rina Dechter covers similar ground but also has chapters that cover topics like local search, tree decomposition methods, optimization, and probabilistic networks more extensively. Dechter's book also contains a chapter by David Cohen and Peter Jeavons on tractability and one by Francesca Rossi on constraint logic programming. There is much in common between the two books. This is perhaps not so surprising since Krzysztof Apt thanks Rina Dechter for much useful discussion that helped him enter the field and start doing research in the area.
Welcome to the On-Line Guide to CONSTRAINT PROGRAMMING designed and maintained by Roman Barták. I have opened this site as an on-line tutorial or, if you want, a textbook for beginners to the area of constraint programming. This area belongs to the less known software technologies but it rapidly evolves and brings a significant commercial interest.
Research on constraints and agents is emerging at the intersection of the communities studying constraint computation and software agents. Constraint-based reasoning systems can be enhanced by using agents with multiple problem-solving approaches or diverse problem representations. The constraint computation paradigm can be used to model agent consultation, cooperation, and competition. An interesting theme in agent interaction, which is studied here in constraint-based terms, is confronting ignorance: the agent's own ignorance or its ignorance of other agents. On the one hand, agent behavior, for example, negotiation, can be modeled as constraint satisfaction and optimization. On the other hand, agents can be used to accomplish constraint satisfaction and optimization, for example, to solve distributed scheduling problems. Agents offer opportunities to apply the constraint computation paradigm and present challenges to extend the paradigm. Constraint computation provides a general ...
The Archive contains many pointers to constraints material. We are in the process of refurbishing it, but recognize that it is incomplete and somewhat out of date. Please contact us if you have any suggestions, contributions or corrections. Brief History: Many thanks to those individuals and organizations that have helped make the Constraints Archive a valuable resource. The Constraints Archive, originally known as the City University Constraints Archive, was created by Michael Jampel; the archive was maintained by David Joslin and Peg Eaton during 1996-1998, when it was split into two entities.
We propose AllDiffPrecedence, a new global constraint that combines together an AllDifferent constraint with precedence constraints that strictly order given pairs of variables. We identify a number of applications for this global constraint including instruction scheduling and symmetry breaking. We give an efficient propagation algorithm that enforces bounds consistency on this global constraint. We show how to implement this propagator using a decomposition that extends the bounds consistency enforcing decomposition proposed for the AllDifferent constraint. Finally, we prove that enforcing domain consistency on this global constraint is NP-hard in general.