Encoding partial constraint satisfaction in the semiring-based framework for soft constraints
Stefano Bistarelli, Eugene C. Freuder, Barry O’Sullivan · 2005
The partial constraint satisfaction paradigm focuses on solving relaxations of problems that either do not admit solutions, or that are either impractical or impossible to solve completely. The semiring-based framework for soft constraints is a unifying model for a variety of extensions of the constraint satisfaction formalism. For example, the semiring-based framework can represent weighted, fuzzy, probabilistic and set-based constraint satisfaction problems. We discuss how the semiring-based framework for soft constraints can be used to model partial constraint satisfaction problems. We show how the semiring framework can be used to capture a notion of distance between a solution and a problem based on the known distance metrics used in the partial constraint satisfaction literature. These solution-problem distance metrics can be seen as providing lower-bounds on the distance between a problem and its relaxation.