Abstract
Constraints appear in many areas of human endeavour starting from puzzles like crosswords (the words can only overlap at the same letter) and recently popular Sudoku (no number appears twice in a row) through everyday problems such as planning a meeting (the meeting room must accommodate all participants) till solving hard optimization problems for example in manufacturing scheduling (a job must finish before another job). Though all these problems look like being from completely different worlds, they all share a similar base – the task is to find values of decision variables, such as the start time of the job or the position of the number at a board, respecting given constraints. This problem is called a Constraint Satisfaction Problem (CSP). Constraint processing emerged from AI research in 1970s (Montanary, 1974) when problems such as scene labelling were studied (Waltz, 1975). The goal of scene labelling was to recognize a type of line (and then a type of object) in the 2D picture of a 3D scene. The possible types were convex, concave, and occluding lines and the combination of types was restricted at junctions of lines to be physically feasible. This scene labelling problem is probably the first problem formalised as a CSP and some techniques developed for solving this problem, namely arc consistency, are still in the core of constraint processing. Systematic use of constraints in programming systems has started in 1980s when researchers identified a similarity between unification in logic programming and constraint satisfaction (Gallaire, 1985) (Jaffar & Lassez, 1987). Constraint Logic Programming was born. Today Constraint Programming is a separate subject independent of the underlying programming language, though constraint logic programming still plays a prominent role thanks to natural integration of constraints into a logic programming framework. This article presents mainstream techniques for solving constraint satisfaction problems. These techniques stay behind the existing constraint solvers and their understanding is important to exploit fully the available technology.
TopBackground
Constraint Satisfaction Problem is formally defined as a triple: a finite set of decision variables, a domain of possible values, and a finite set of constraints restricting possible combinations of values to be assigned to variables. Although the domain can be infinite, for example real numbers, frequently, a finite domain is assumed. Without lost of generality, the finite domain can be mapped to a set of integers which is the usual case in constraint solvers. This article covers finite domains only. In many problems, each variable has its own domain which is a subset of the domain from the problem definition. Such domain can be formally defined by a unary constraint. We already mentioned that constraints restrict possible combinations of values that the decision variables can take. Typically, the constraint is defined over a subset of variables, its scope, and it is specified either extensionally, as a set of value tuples satisfying the constraint, or intentionally, using a logical or arithmetical formula. This formula, for example A < B, then describes which value tuples satisfy the constraint. A small example of a CSP is ({A, B, C}, {1, 2, 3}, {A < B, B < C}).
The task of constraint processing is to instantiate each decision variable by a value from the domain in such a way that all constraints are satisfied. This instantiation is called a feasible assignment. Clearly, the problem whether there exists a feasible assignment for a CSP is NP-complete – problems like 3SAT or knapsack problem (Garey & Johnson, 1979) can be directly encoded as CSPs. Sometimes, the core constraint satisfaction problem is accompanied by a so called objective function defined over (some) decision variables and we get a Constrained Optimisation Problem. Then the task is to select among the feasible assignments the assignment that minimizes (or maximizes) the value of the objective function. This article focuses on techniques for finding a feasible assignment but these techniques can be naturally extended to optimization problems via a well-known branch-and-bound technique (Van Hentenryck, 1989).
Key Terms in this Chapter
Decision Variable: A variable modelling some feature of the problem, for example a start time of activity, whose value we are looking for in such a way that specified constraints are satisfied.
Search Algorithms: Algorithms that explore the space of possible (partial or complete) instantiations of decision variables with the goal to find an instantiation satisfying all the constraints (and optimizing the objective function in case of COP).
Domain of Variable: A set of possible values that can be assigned to a decision variable, for example a set of times when some activity can start. Constraint processing usually assumes finite domains only.
Global Constraint: An n-ary constraint modelling a subset of simpler constraints by providing a dedicated filtering algorithm that achieves stronger or faster domain pruning in comparison to making the simpler constraints (locally) consistent. All-different is an example of a global constraint.
Constraint Satisfaction Problem (CSP): A problem formulated using a set of decision variables, their domains, and constraints between the variables. The task is to find an instantiation of decision variables by values from their domains in such a way that all the constraints are satisfied.
Constraint: Any relation between a subset of decision variables. Can be expressed extensionally, as a set of value tuples satisfying the constraint, or intentionally, using an arithmetical or logical formula between the variables, for example A+B?
Constrained Optimisation Problem (COP): A Constraint Satisfaction Problem extended by an objective function over the (subset of) decision variables. The task is to find a solution to the CSP which minimizes or maximizes the value of the objective function.
Domain Pruning (Filtering): A process of removing values from domains of variables that cannot take part in any solution. Usually, due to efficiency issues only the values locally violating some constraint are pruned. It is the most common type of consistency technique.
Consistency Techniques: Techniques that remove inconsistent values (from variables’ domains) or value tuples, that is, the values that cannot be assigned to a given variable in any solution. Arc consistency is the most widely used consistency technique.
Look Ahead: The most common technique for integrating depth-first search with maintaining consistency. Each time a search decision is done, it is propagated in the problem model by making the model consistent.