14.2  Background: Constraint Satisfaction Problems

There is a large body of scientific work and literature about Constraint Satisfaction Problems, or CSPs. CSPs are a restricted class of constraint problems with the following properties

• there is a fixed set of variables X₁, ..., X_n
• every variable X_i has a finite domain D_i of values that the variable is allowed to take. In general, this can be an arbitrary, unordered domain.
• usually one considers only binary (2-variable) constraints c_ij(X_i,X_j). Every constraint is simply defined as a set of pairs of consistent values.
• the problem is to find a valuation (labeling) of the variables such that all the constraints are satisfied.

The restriction to binary constraints is not really limiting since every CSP can be transformed into a binary CSP. However, this is often not necessary since many algorithms can be generalised to n-ary constraints.

A CSP network is the graph formed by considering the variables as nodes and the constraints as arcs between them. In such a network, several levels of consistency can be defined:

Node consistency

∀v ∈ D_i : c_i(v) (not very interesting). It means that all unary constraints are reflected in the domains

Arc consistency

∀v ∈ D_i ∃w ∈ D_j : c_ij(v,w) (most practically relevant). It means that for every value in the domain of one variable, there is a compatible value in the domain of the other variable in the constraint. In practice, constraints are symmetric, so the reverse property also holds.

Path consistency

∀v ∈ D_i ∀w ∈ D_j ∃u ∈ D_k : c_ik(v,u), c_kj(u,w) (usually too expensive). One can show that this property extends to whole paths, i.e. on any path of constraints between variables i and j the variables have domain values which are compatible with any domain values for i and j.

Note that neither of these conditions is sufficient for the problem to be satisfiable. It is still necessary to search for solutions. Computing networks with these consistency levels can however be a useful intermediate step to finding a solution to the CSP.

Consequently, a complete CSP solver needs the following design decisions:

• what level of consistency do we want to employ?
• at what time during search do we want to (re)establish this consistency?
• what algorithm do we use to establish this consistency?

In practice, the most relevant consistency level is arc-consistency. Consequently, a number of algorithms have been proposed for the purpose of establishing arc-consistency. The algorithms used in ECLⁱPS^e are mostly variants of AC-3 [16] and AC-5 [10].