constraint learning

enhancement of backtracking

principle: if a subproblem is inconsistent, better find it out early

applied to backtracking:

reach a node, choose a variable, do the same in the children, etc.
find inconsistency in all 9215 descendant leaves
reach the same node, immediately recognize that the current assigment cannot be extended to satisfy all constraints

second is better, avoid visiting 9215 nodes

how?

learn constraint

if no satisfying assignment in the descendant of a node
⇓
better find that out immediately than visiting many descendants

how: during the search, learn new constraints

consequences of original constraints ⇒ have to be satisfied anyway

if they are falsified in a node ⇒ no satisfying assigment from the node
detected immediately, without visiting the subtree

an example

a part of the tree of recursive calls:

in the leaves, x₁ = 1 and x₄ = 2 suffice for inconsistency
example: constraints x₁ ≥ x₅ and x₅ ≥ x₄

new constraint scope: x1 and x4 relation: all pairs of values but x₁ = 1 e x₄ = 2 what for? a possible situation during the rest of the search the new constraint allows cutting the search short same result as... choose x₅ as the variable after x₄ = 2 but: requires recognizing that x₅ is the best variable at this point more than two variables may need to be evaluated to reach inconsistency this case: only x₅ conflicting needs more constraints ⇒ search is cut more often ⇒ quicker more constraints ⇒ longer time to check all of them ⇒ slower learn a constraint only if its usefulness (search cuts) is reckoned larger than its cost (checking at ever other node) reckoned: no way to know in advance to reckon = stimare constraint: usefulness vs. cost automatically created constraint have the form: exactly one tuple is not allowed for such constraints, shorter means: more likely to be falsified easier to check but mostly 1. bounded learning only create a constraint if its variables are below a certain bound example: only create constraint of at most 3 variables this is the 3-bounded learning relevance-bounded learning discard learned constraints when they no longer seem useful each learned constraints forbids a single assigment forbiden assigment is very different from the current assigment ⇓ constraint is unlikely to be still useful relevance bounded learning of order i: discard a learned constraint if its forbidden assigment differs from the current assignment on i variables differs = variables assigned in both, but to different values constraints that can be learned which constraints are true, and can therefore be learned? backjumping produces sets of variables that are sufficient for inconsistency consider for learning: constraints forbidding the current assigment to these assignments