I am working on an algorithm which calculates intervals for variables in some given constraints. For example there is a function called propagateValues and its description is
Propagate value ranges for the given constraints
What exactly is meant by value propagation ?
The algorithm I am working is basically trying to simplify sets of constraints by doing a range/interval analysis before querying the solver for a feasible solution (to make solving constraint sets more efficient)
1
In constraint satisfaction, propagation means to make explicit a truth condition that is already present in the problem, but only implicitly.
For instance, if you have a variable that must be even, and another that has to be greater than 10, those are constraints on the two variables. Nothing else is known about the solution. However, if you have another binary constraint stating that the first variable has to be greater than twice the value of the second, then the value range of the first variable is actually 20, 22, 24… rather than 0, 2, 4, 6…
Propagating means finding such a range that is smaller than it first appears (usually by evaluating more than one constraint simultaneously), and then adjusting the value set for one variable to the stronger condition. It can go a long way towards solving a constraint satisfaction problem, or at least make it more efficient to enumerate all solutions.
1