Constraint Satisfaction Problems

Definition

A constraint satisfaction problem consist of three components, $X$, $D$ and $C$:

• $X$ is a set of variables, $\left\{X_1,\dots ,X_n\right\}$
• $D$ is a set of domains, $\left\{D_1,\dots ,D_n\right\}$, one for each variable
• $C$ is a set of constraints that specify allowable combination of values. Each domain $D_i$ consists of a set of allowable values, $\left\{v_1,\dots ,v_k\right\}$ for variable $X_i$. Each constraint $C_i$ consists of a pair $⟨\text{scope},\text{rel}⟩$, where scope is a tuple of variables that participate in the constraint and rel is a relation that defines the values that those variables can take on.

To solve a CSP, we need to define a state space and the notion of a solution. Each state in a CSP is defined by an assignment of values to some or all of the variables, $\left\{X_i=v_i,X_j=v_j,\dots \right\}$. An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned, and a solution to a CSP is a consistent, complete assignment. A partial assignment is one that assigns values to only some of the variables.

Constraint Hypergraph

In a constraint hypergraph

• Nodes represent variables.
• Hyperedges represent constraints. A hyperedge is like an edge, but it can connect any number of nodes (not just two). Each hyperedge connects all the variables involved in a particular constraint.

Example: Suppose you have the following CSP:

• Variables: $X,Y,Z,W$
• Domains: $D_X=\{1,2\},D_Y=\{1,2\},D_Z=\{1,2\},D_W=\{1,2\}$
• Constraints:
  • $C_1:X+Y+Z=4$
  • $C_2:Z<W$ The constraint hypergraph would have four nodes (for $X,Y,Z,W$). It would have two hyperedges:
• One hyperedge connects $X,Y,$ and $Z$ (representing $C_1$).
• One hyperedge connects $Z$ and $W$ (representing $C_2$).

Constraint Propagation

Note

CSPs can indeed be solved by naive DFS and BFS, but the time consumption might be relatively high. Constraint propagation aims to reduce the domain size of the variables, so that there would be less chance that we would change the values of the assigned variables.

In CSPs, algorithms can perform search (variable assignment) or constraint propagation (inference to reduce variable domains). Constraint propagation can sometimes solve the problem without search.

Node consistency

A single variable (corresponding to a node in the CSP network) is node-consistent if all values in its domain satisfy its unary constraints. For example, in map coloring, if SA's domain is $\{\text{red},\text{green},\text{blue}\}$ and SA dislikes green, node consistency reduces the domain to $\{\text{red},\text{blue}\}$.

CSPs can be simplified by enforcing node consistency and transforming $n$-ary constraints into binary ones.

Arc consistency

A variable $X_i$ is arc-consistent with respect to $X_j$ if every value in $D_i$ has a corresponding value in $D_j$ that satisfies the binary constraint $(X_i,X_j)$.

Example: For $Y=X^2$ with domains $\{0,1,2,3,4,5,6,7,8,9\}$, enforcing arc consistency reduces $X$'s domain to $\{0,1,2,3\}$ and $Y$'s to $\{0,1,4,9\}$.

Path consistency

A pair $\{X_i,X_j\}$ is path-consistent with respect to $X_m$ if for every consistent assignment $(X_i,X_j)$, there exists a value for $X_m$ that satisfies constraints with both $X_i$ and $X_j$.

K-consistency

A CSP is $k$-consistent if any consistent assignment to $k-1$ variables can be extended to a $k$-th variable.

• 1-consistency = node consistency.
• 2-consistency = arc consistency.
• 3-consistency = path consistency. Strong $k$-consistency: $k^{\prime }$-consistency for all $k^{\prime }\le k$.
• A strongly $n$-consistent CSP can be solved in $O(n^{2}d)$ time without backtracking, where $d$ is the domain size at most.
• Trade-off: Higher $k$ requires exponential time/space.

Other constraints

A global constraint is one involving an arbitrary number of variables. For example, the Alldiff constraint says that all the variables involved must have distinct values.

The resource constraint, sometimes called the at most constraint limits the maximum value of a variable.

Arc Consistency Algorithms

AC-3 Algorithm

• Uses a queue of arcs to enforce consistency.
• If a domain is revised, neighboring arcs are rechecked.
• Time complexity: $O(c{d}^3)$ for $c$ constraints and domain size $d$.

AC3 reduces the domain by checking if an assignment of a variable is compatible with its neighboring variables (does not violate constraints). When no situation can be found where this assignment is compatible with neighboring variables, this value is removed from the domain of the variable.

Local Search

The initial state assign a value to every variable, and the search changes the value of one variable at a time.

In choosing a new value for a variable, the most obvious heuristic is to select the value that results in the minimum number of conflicts with other variables—the min conflicts heuristic.

The Structure of CSPs

Subproblems

Independent Subproblems: any solutions of all the subproblems can be combined into a solution of the whole problem. There are no conflicts between two different subproblems.

Independence can be ascertained simply by finding connected components of the constraint graph.

Dividing the whole problem into subproblems can help reduce time complexity.

Tree-structured CSPs

To solve a tree-structured CSP, first pick any variable to be the root of the tree, and choose an ordering of the variables such that each variable appears after its parent in the tree. Such an ordering is called a topological sort.