Constraint learning: Difference between revisions

Revision as of 16:05, 10 February 2006

Revision as of 16:11, 10 February 2006

Line 20:

|}

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 backtracking avoids doing useless search. As a result, smallSmall inconsistent subsets of the current partial solution are preferredusually better overthan large ones, 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.

Size is however not the only feature of learned constraints to take into account. Indeed, a small constraint may be useless in a particular state of the search space because the values that violate it will not be encountered again. A larger constraint whose violating values are more similar to the current partial assignment may be preferred in such cases.

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