Constraint propagation is used in constraint satisfaction problems to “look ahead” at unassigned variables in the search to try to detect obvious failures, so that a backtracking algorithm doesn’t expand a section of the search tree that violates the constraints.
Even if it doesn’t detect an obvious failure, it might be possible to eliminate parts of the future search by pruning domains of variables. Propagation has to be applied during the search, potentially at every node of the search tree. It’s an inference step that needs time. If propagation is slow, this can slow the search down to the point where finding a solution takes longer.
There are two main types of propagation:
Heuristics
Heuristic functions can be used to determine (1) the order in which variables are assigned, and (2) the order of values tried for each variable. Oftentimes the chosen variable may tremendously impact performance.
Some possible heuristics:
- Degree — we select the variable that is involved in the largest number of constraints on other unassigned variables.
- Minimum remaining values (MRV) — we always branch on a variable with the smallest remaining values (i.e., the smallest current domain).
- The intuition behind this is that if variables have only one value left, then the value is effectively forced so we should propagate its consequences immediately.
- More constraint propagation (DWO) failures occur when the tree selects variables with larger domains. We can find inconsistencies much faster.
- Least constraining value — we always pick a value in the current domain that rules out the least domain values of other neighbouring variables in the constraint.
- This maximises the flexibility for subsequent variable assignments.