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.
MiniZinc provides a solver-independent modeling language that is now supported by constraint-programming solvers, mixed integer programming solvers, SAT and SAT modulo theory solvers, and hybrid solvers. Every year since 2008 we have run the MiniZinc Challenge, which compares and contrasts the different strengths of different solvers and solving technologies on a set of MiniZinc models. Here we report on what we have learned from running the competition for 6 years. MiniZinc is high level enough to express most combinatorial optimization problems easily and in a largely solverindependent way; for example, it supports sets, arrays, and user-defined predicates, some overloading, and some automatic coercions. However, MiniZinc is low level enough that it can be mapped easily onto many solvers.