Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This may be a stupid question but 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)

share|improve this question
    
try asking on math.se? –  gbjbaanb Jul 26 '12 at 11:49

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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