Constraint learning: Difference between revisions

Revision as of 20:16, 27 September 2006

Revision as of 01:05, 12 November 2006

Line 1:

In [[constraint satisfaction problem|constraint satisfaction]] [[backtracking]] [[algorithm]]s, '''constraint learning''' is a techinquetechnique 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==

Line 38:

==Jumpback learning==

Jumpback learning is based on storing as constraints the inconsistent assignments that would be found by [[conflict-based backjumping]]. Whenever a partial assignment is found inconsistent, this algorithm selects the violated constraint that is minimal according to an ordering based on the order of instantiation of variblesvariables. The evaluation restricted of the variables that are in this constraint is inconsistent and is usually shorter than the complete evaluation. Jumpback learning stores this fact as a new constraint.

The ordering on constraints is based on the order of assignment of variable. In particular, the least of two constraint is the one whose latest non-common variable has been instantiated first. When an inconsistent assignment is reached, jumpback learning selects the violated constraint that is minimal according to this ordering, and restricts the current assignment to its variables. The constraint expressing the inconsistency of this assignment is stored.