Combining Branch&Bound and SBDD to solve Soft CSPs
Stefano Bistarelli, Barry O’Sullivan · 2004
Exploiting symmetry in constraint satisfaction problems has become a very popular topic of research in recent times. The existence of symmetry in a problem has the effect of artificially increasing the size of the search space that is explored by search algorithms. Another significant topic of research has been the development of approaches to reasoning about preferences. As constraint processing applications are becoming more widespread in areas such as electronic commerce, configuration, etc., it is becoming increasingly important that we can reason about preferences as efficiently as possible. In this paper we extend some existing results dealing with symmetry in the semiring framework for soft constraints. In particular we extend existing definitions of symmetry to partial instantiations. We present Soft-SBDD, a generalization of Symmetry Breaking via Dominance Detection, and present theoretical results demonstrating that symmetry breaking in soft constraint satisfaction problems improves the efficiency of search.