Constraint Satisfaction Problems (CSP)

$$\bold{P} = (X, B, C)$$

With:

• $X=\{x_1, ..., x_n\}$: set of variables

• $B=\{D_1, ..., D_N\}$: set of domains, with $x_i \in D_i$.

• $C=\{c_1, ..., c_n\}$: set of constraints, with $c_j=(S_j; \hspace{0.2em} R_j)$, where $S_j$ is the scope (set of involved variables) and $R_j$ is a relation such that $R \subset D_{h_{1}} \times ... \times D_{h_{*}}$.

Assignments

The goal is to assign values to satisfy all constraints. An assignment is a set $\{(x_k, v_k) : x_k \in X, v_k \in D_k\}$. Properties:

• complete if $|A|=n$ (otherwise it's partial).

• consistent if it satisfies all constraints.

Notes

• A variable $x_i$ is said to be node-consistent (or 1-consistent) if it satisfies all unary constraints.

• A variables $x_i$ is said to be arc-consistent (or 2-consistent) w.r.t to $x_j$ (and vice versa) if they satisfy all binary constraints regarding each other.

AC-3

Idea: we take one constraint at a time, we find values of $x_i$ that does not satisfy that constraint (node consistency check) . Note that this is applicable only on binary domains.

def AC3(constraints):
	queue <- constraints
	while queue is not empty:
    <xi -> xj> = queue.pop()
    arc_consistency()	// removal of x_i values that does not satisfy c
    if domain is changed:
    	if len(domain) == 0: return False
    else:
    	for <xk -> xi> and k != j:
    	queue.push(xk -> xi)
  return True	// if we manage to get out of the loop (queue empty)
  						// without emptying the domain, we're done    

Basically we start from the constraint list, we pop one constraint at a time. When we find some value from the domain which does not satisfy the constraints (for e.g. in the constraint list of x2->x3 ther's not the variable b, which belong to the domain of x3, we remove b from the domain), we take all constraints that contain b and we check if the other variable appear in other constraints of the same list. If not, we remove also those, and we keep going until we stop modifying the domain.

Backtracking search (BTS)

Node consistency check, similar to DFS: it generates a single successor starting from the root until we get to a leaf. At that point we can start backtracking. The idea is to try every possible combination of variable-domain pairs compatible with the given constraints. It is commutative, which means that the order in which values are assigned to the variables has no impact on the possibility of reaching consistent and complete assignments. Pseudocode:

bts(A):
  if assignment A is complete: return A
  X <- random variable not in A
  D <- order of values in the domain of X
  for each v in D: 
  	add (X <- v) to A
  	if A is consistent:
  		result <- bts(A)
  		if result ≠ failure: return result
  	remove (X <- v) from A
  return failure

Forward checking

We also apply arc consistency when generating child nodes. This means that we need to check which variables are still available at each node generation to avoid expanding useless nodes (given the set of contraints and given already selected domain values we strip variables that do not satisfy constraints).

Variable ordering heuristics

• Minimum remaining value (MRV): it prefers variable assignment with smaller domain size, ties broken in lexicographical order. This means that after applying AC-3 to the problem we will select in the root node the variable with the smallest remaining domain.

• Least costraining value (LCV): Applied after choosing which variable assignment (so which variable to use in the next step). This means that it can (and should) be used in conjunction with MRV. It tells in which order to consider the domain elements of the variable, by counting the number of variables of the other domains that become unavalaible after fixing a value from the domain elements. It prefers variables with smaller ruled out set ($\min|RO_i|$), of course.