Constraint learning

In constraint satisfaction backtracking algorithms, constraint learning is a techinque for imporoving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the search space, as future partial evaluations may be found inconsistent without further search. Clause learning is the name of this technique when applied to propositional satisfiability.

Definition

Backtracking algorithms work by choosing an unassinged variable and recursively solve the problems obtained by assigning a value to this variable. Whenever the current partial solution is found inconsistent, the algorithm goes back to the previously assigned variable, as expected by recursion. A constraint learning algorithm differs because it tries to record some information, before backtracking, in form of a new constraint. This can reduce the further search because the subsequent search may encounter another partial solution that is inconsistent with this new constraint. If the algorithm has learned the new constraint, it will backtrack from this solution, while the original backtracking algorithm would do a subsequent search.

If the partial solution $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ is inconsistent, the problem instance implies the constraint stating that $x_{i}=a_{i}$ cannot be be true for all $i\in [1,k]$ at the same time. However, recording this constraint is not useful, as this partial solution will not be encountered again due to the way backtracking proceed.

On the other hand, if a subset of this evaluation is inconsistent, the corresponding constraint may be useful in the subsequent search, as the same subset of the partial evaluation may occur again in the search. For example, the algorithm may enounter an evaluation extending the subset $x_{2}=a_{2},x_{5}=a_{5},x_{k-1}=a_{k-1}$ of the previous partial evaluation. If this subset is inconsistent and the algorithm has stored this fact in form of a constraint, no further search is needed to conclude that the new partial evaluation cannot be extended to form a solution.

Search has reached a dead end.	Inconsistency may be caused by the values of $x_{1}$ and $x_{4}$ only. This fact can be stored in a new constraint.	When reaching the same values of $x_{1}$ and $x_{4}$, the new constraint blocks the search.

The efficiency of constraint learning algorithm is balanced between two factors. On one hand, the more often a recorded constraint is violated, the more often block backtracking from doing useless search. As a result, algorithms search for small inconsistent subset of the current partial solution, as they correspond to constraints that are easier to violate. On the other hand, finding a small inconsistent subset of the current partial evaluation may require time, and the benefit may not be balanced by the subsequent reduction of the search time.

Various constraint learning technique exist, differing in strictness of recorded constraints and cost of finding them.

Graph-based learning

Graph-based learning uses the same rationale of graph-based backjumping: if the algorithm proves all values of $x_{k+1}$ to be inconsistent with $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$, then this evaluation was consistent, as otherwise the algorithm would not have evaluated $x_{k+1}$ at all; as a result, the constraints violated by a value of $x_{k+1}$ together with $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ all contain $x_{k+1}$.

As a result, a small inconsistent partial evaluation can be found by restricting $x_{1},\ldots ,x_{k}$ to variables that are in a constraint with $x_{k+1}$, provided that this constraint contains no unassigned variable.

This method is called "graph-based" because the information on which pairs of variables are in the same constraint can be found out from the graph associated to the constraint satisfaction problem.

See also

• Look-ahead (backtracking)
• Backjumping

Reference

• http://www.ics.uci.edu/~dechter/books/index.html. {{cite book}}: Missing or empty |title= (help); Unknown parameter |First= ignored (|first= suggested) (help); Unknown parameter |Last= ignored (|last= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help) ISBN 1-55860-890-7