A new local consistency for weighted CSP dedicated to long domains
Matthias Zytnicki, Christine Gaspin, Thomas Schiex · 2006
The weighted constraint satisfaction problem (WCSP) is a soft constraint framework with a wide range of applications. Most current complete solvers can be described as a depth-first branch and bound search that maintains 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 the 2B-consistency, a weaker form of arc consistency well-known in classic CSPs, into the bound arc consistency and we provide several algorithms to enforce it.