Bound arc consistency for weighted CSPs

Abstract. WCSP is a soft constraint framework with a wide range of applications. Most current complete solvers can be described as a depthfirst branch and bound search that maintain some form of local consistency during the search. However, the known consistencies are unable to solve problems with huge domains because of their time and space complexities. In this paper, we adapt a weaker form of arc consistency, well-known in classic CSPs, called the bound arc consistency and we provide several algorithms to enforce it.