Constraint satisfaction---a survey
Zsófia Ruttkay · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1998
Constraint satisfaction has been used as a term to cover a wide range of methods to solve problems stated in the form of a set of constraints.As the general constraint satisfaction problem (CSP) is NP-complete, initially the research focused on developing new and more efficient solution methods, resulting in an arsenal of algorithms.Recently, much attention has been paid on how to finetune the use of this arsenal, and to be able to judge which methods are promising for a given problem or problem-type.In the last few years different generalisations of the classical CSP have got much attention too, allowing to model a wider range of every-day problems.In this survey we introduce the classical CSP and the basic solution techniques as well as the ongoing research on the applicability of these methods and on extensions of the classical framework.After giving some introductory examples we define the most essential technical notions in order to explain different solution methods.First, we discuss constraint propagation algorithms, which transform the initially given CSP step by step to an equivalent, but smaller problem.Then we will introduce a family of constructive search algorithms, followed by methods exploiting the structure of the problem.Finally, we discuss the local and stochastic methods, also applicable to solve non-standard problems.The discussion of solution methods will be closed by addressing the issue of choosing a good algorithm for a given problem.Many practical applications have essential characteristics which do not "fit into" the classical formalism of CSP.The extension of the problem definition and appropriate solution methods will be dealt with in the final chapter.