Constraint Satisfaction Problems

Constraint satisfaction is the process of finding models of variable assignments that are consistent with a set of constraints (equations, inequalities, etc.) defined on these variables.

Defining CSPs §

A Constraint Satisfaction Problem (CSP) is defined by three components:

• $X$ is a set of variables $\{X_1,...,X_n\}$,
• $D$ is a set of domains for these variables $\{D_1,...,D_n\}$,
• $C$ is a set of constraints on these variables.

Formally, we may consider $C$ to be a set of pairs $(s,r)$, where $s$ is a tuple of variables from $X$ which are used in this constraint, and $r$ is a relation defining the set of tuples which may be assigned to the variables. $r$ may be defined as a set of allowed variables, or more commonly as a function which computes whether a given tuple is a member of the relation.

Constraint Graphs §

It can be useful to consider a CSP a constraint graph, where each node is a variable and edges join every pair of nodes participating in a common constraint.

We can categorise constraint graphs in certain helpful ways:

Node consistency §

A single variable in a CSP is node-consistent if and only if all the values in its domain satisfy any unary constraints defined on the variable. It is simple to achieve node-consistency by initially removing any values from a variable’s domain which would violate any of its unary constraints. Once this has been done, the unary constraints can be safely removed from the set of constraints. Node consistency is a common assumption by CSP solvers.

Arc consistency §

A single variable in a CSP is arc-consistent if and only if all the values in its domain satisfy any binary constraints defined on the variable. A variable $X_i$ is arc-consistent with another variable $X_j$ if, for every value in $D_i$, there exists a value in $D_j$ which satisfies the binary constraint on the arc $(X_i,X_j)$. A graph is said to be arc-consistent if every variable is arc-consistent with every other variable.

Directed Arc Consistency §

The notion of arc consistency on a CSP is often unnecessarily strict, and it suffices to have arc consistency only with respect to some ordering of variables $X_1,...,X_n$. A CSP is directed arc-consistent if and only if, under this ordering, every $X_i$ is arc-consistent with every $X_j$ where $j>i$.

Path consistency §

A pair of variables $(X_i,X_j)$ in a CSP are path-consistent with respect to a third variable $X_k$ if, for every permissible assignment $\{X_i=a,X_j=b\}$, there exists an assignment to $X_k$ which satisfies any constraints on $\{X_i,X_k\}$ and $\{X_k,X_j\}$. This can be seen as the consistency of a path between $X_i$ and $X_j$ with $X_k$ in the middle.

Directed Path Consistency §

Similarly to with arc consistency, we can introduce a directed version of path consistency. A CSP is directed path-consistent if and only if, for some ordering of variables $X_1,...,X_n$, there exists $a_k\in D_k$ such that $(a_i,a_k)\in R_{i,k}$ and $(a_j,a_k)\in R_{j,k}$ for any indices $i<j<k$ and any pair of elements $a_i\in D_i$ and $a_j\in D_j$ such that $(a_i,a_j)\in R_{i,j}$.

K-consistency §

This notion of consistency can be extended further, and defined generally as k-consistency. A CSP is said to be k-consistent if, for any set of $k-1$ variables and a permissible assignment to those variables, a consistent assignment can always be made to any $k$th variable. A CSP is strongly k-consistent if it is $n$-consistent for all $n\in \mathbb{N},n\le k$. If we have a CSP with $n$ nodes which is strongly $n$-consistent, then we can obtain a solution by considering each node in turn (in any order), and selecting the first value from its domain which is consistent with all previous selections. Unfortunately, enforcing strong k-consistency is a complex task, and as such this is generally not a feasible method for solving a CSP. We can extend the notion of directed consistency to k-consistency and strong k-consistency as described above.

Global constraints §

A global constraint is a constraint with a generalised definition that can be applied to an arbitrary number of variables. Perhaps the most common global constraint is “alldiff”, which requires that every variable participating takes a value different from any other participating variable.

We can often introduce specific shortcuts for determining inconsistencies in global constraints. For example, the “alldiff” constraint cannot be satisfied for $m$ variables if $m<n$, where $n$ is the size of the union of the domains for each variable. Similarly, $Atmost(k,X_1,...X_n)$ cannot be satisfied if $(\sum _{i=0}^{n}min(D_i))<k$. In this way we can also enforce consistency, removing the maximum value from each domain, if this value is not consistent with the minimum values from every other domain.

Solving CSPs §

Once we have applied optimisations and constraint propagation, we may still have variables with multiple possible values. In this case, we much search for a solution. There are many searching techniques applicable, perhaps most obviously a backtracking search. In order to ensure that the search tree has $n^d$ leaves (rather than $n!n^d$), at each level we select a single variable to consider. As such, we can optimise this decision.

The most common method for variable ordering is the minimum-remaining-value (MRV) heuristic, which selects the variable with the fewest remaining legal values at every decision point. When the MRV heuristic does not result in an obvious selection, which often occurs at the beginning of the search, the degree heuristic can be used to make a selection. This function selects the variable involved in the greatest number of constraints with other unassigned variables.

Another important decision to make is the ordering of values to consider for an individual variable. The least-constraining-value heuristic orders values by the number of choices for neighbouring variables ruled out by the selection of this variable. This can be seen as always trying to leave the greatest number of options for future decisions.

Note

These two strategies have opposing priorities - variables are ordered in a fail-first manner and values fail-last. As every variable must be assigned, choosing the most likely to fail reduces the number of successful assignments over which we will have to backtrack. As we are looking for only a single solution, we can look first at the values most likely to lead to a solution.