In artificial intelligence and operations research, a Weighted Constraint Satisfaction Problem (WCSP) is a generalization of a constraint satisfaction problem (CSP) where some of the constraints can be violated (according to a violation degree) and in which preferences among solutions can be expressed. This generalization makes it possible to represent more real-world problems, in particular those that are over-constrained (no solution can be found without violating at least one constraint), or those where we want to find a minimal-cost solution (according to a cost function) among multiple possible solutions.
Contents
Formal definition
A Weighted Constraint Network (WCN) is a triplet
Each soft constraint
In WCSP, specific subclass of Valued CSP (VCSP), costs are combined with the specific operator
Without any loss of generality, the existence of a nullary constraint
The total cost of an instantiation
Considering a WCN, the usual (NP-hard) task of WCSP is to find a complete instantiation with a minimal cost.
Approach with cost transfer operations
Node consistency (NC) and Arc consistency (AC), introduced for the Constraint Satisfaction Problem (CSP), have been studied later in the context of WCSP. Furthermore, several consistencies about the best form of arc consistency have been proposed: Full Directional Arc consistency (FDAC), Existential Directional Arc consistency (EDAC), Virtual Arc consistency (VAC) and Optimal Soft Arc consistency (OSAC).
Algorithms enforcing such properties are based on Equivalence Preserving Transformations (EPT) that allow safe moves of costs among constraints. Three basic costs transfer operations are:
The goal of Equivalence Preserving Transformations is to concentrate costs on the nullary constraint
Approach without cost transfer operations
An alternative to cost transfer algorithms is the algorithm PFC-MRDAC which is a classical branch and bound algorithm that computes lower bound
Resolution of n-ary WCSPs
Cost transfer algorithms have been shown to be particularly efficient to solve real-world problem when soft constraints are binary or ternary (maximal arity of constraints in the problem is equal to 2 or 3). For soft constraints of large arity, cost transfer becomes a serious issue because the risk of combinatorial explosion has to be controlled.
An algorithm, called
Benchmarks
Many real-world WCSP benchmarks are available on http://costfunction.org/en/benchmark and on http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.