Weighted constraint satisfaction problem

A Weighted Constraint Network (WCN), aka Cost Function Network (CFN), is a triplet ${\displaystyle \langle X,C,k\rangle }$ where ${\displaystyle X}$ is a finite set of discrete variables, ${\displaystyle C}$ is a finite set of soft constraints and ${\displaystyle k>0}$ is either a natural integer or ${\displaystyle \infty }$.

Each soft constraint ${\displaystyle c_{S}\in C}$ involves an ordered set ${\displaystyle S}$ of variables, called its scope, and is defined as a cost function from ${\displaystyle l(S)}$ to ${\displaystyle \langle 0,...,k\rangle }$ where ${\displaystyle l(S)}$ is the set of possible instantiations of ${\displaystyle S}$. When an instantiation ${\displaystyle I\in l(S)}$ is given the cost ${\displaystyle k}$, i.e., ${\displaystyle c_{S}(I)=k}$, it is said forbidden. Otherwise it is permitted with the corresponding cost (0 being completely satisfactory).

In WCSP, specific subclass of Valued CSP (VCSP),[1] costs are combined with the specific operator ${\displaystyle \oplus }$ defined as: ${\displaystyle \forall \alpha ,\beta \in \langle 0,...,k\rangle ,\alpha \oplus \beta =min(k,\alpha +\beta )}$. The partial inverse of ${\displaystyle \oplus }$ is ${\displaystyle \ominus }$ defined by: if ${\displaystyle 0\leq \beta \leq \alpha <k}$, ${\displaystyle \alpha \ominus \beta =\alpha -\beta }$ and if ${\displaystyle 0\leq \beta <k}$, ${\displaystyle k\ominus \beta =k}$.

Without any loss of generality, the existence of a nullary constraint ${\displaystyle c_{\emptyset }}$ (a cost) as well as the presence of a unary constraint ${\displaystyle c_{x}}$ for every variable ${\displaystyle x}$ is assumed.

The total cost of a complete instantiation ${\displaystyle I\in l(X)}$ is the bounded sum of the cost of ${\displaystyle I}$ on ${\displaystyle c_{S}}$ for all soft constraint ${\displaystyle c_{S}\in C}$, including the nullary cost ${\displaystyle c_{\emptyset }}$ and the unary costs for ${\displaystyle I}$ of the variables in ${\displaystyle X}$.

Considering a WCN/CFN, the usual (NP-hard) task of WCSP is to find a complete instantiation with a minimal cost. Other tasks in the related field of graphical model can be defined.[2]

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 ${\displaystyle GAC^{w}-WSTR}$,[9] has been proposed to enforce a weak version of the property Generalized Arc Consistency (GAC) on soft constraints defined extensionally by listing tuples and their costs. This algorithm combines two techniques, namely, Simple Tabular Reduction (STR)[10] and cost transfer. Values that are no longer consistent with respect to GAC are identified and minimum costs of values are computed. This is particularly useful for efficiently performing projection operations that are required to establish GAC.

Global cost functions with a dedicated semantic (e.g. SoftAllDifferent, SoftAmong) and polytime complexity have been also studied.[11]

• https://www.ics.uci.edu/~dechter/software.html
• https://miat.inrae.fr/toulbar2 (based on cost transfer operations)

Many real-world WCSP benchmarks are available on http://genoweb.toulouse.inra.fr/~degivry/evalgm[12] and https://forgemia.inra.fr/thomas.schiex/cost-function-library (older version at http://costfunction.org/en/benchmark). More MaxCSP benchmarks available on http://www.cril.univ-artois.fr/~lecoutre/#/benchmarks (deprecated site, see also http://xcsp.org/series).

• Constraint satisfaction problem
• Constraint programming
• Preference-based planning