Node and Arc Consistency in Weighted CSP

Recently, a general definition of arc consistency (AC) for soft constraints has been proposed. In this paper we specialize this definition to weighted CSP and introduce a O(ed3) algorithm. Then, we refine the definition and introduce a stronger form of arc consistency (AC*) along with a O(n2 d3) algorithm. We empirically demonstrate that AC* is likely to be much better than AC in terms of pruned values.