CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation

This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(ρ), ranging from belief propagation (ρ 0) to (pure) survey propagation(ρ 1).