1

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)

  • try asking on math.se? – gbjbaanb Jul 26 '12 at 11:49
3

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.

  • Thanks this makes sense. 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) – Cemre Jul 26 '12 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.