Weighted constraint satisfaction problem: Difference between revisions

Revision as of 10:05, 15 September 2021

Latest revision as of 13:49, 15 July 2024

(6 intermediate revisions by 3 users not shown)

Line 1:

In [[artificial intelligence]] and [[operations research]], a '''Weighted Constraint Satisfaction Problem''' ('''WCSP'''), also known as '''Valued Constraint Satisfaction Problem''' ('''VCSP'''), is a generalization of a [[constraint satisfaction problem]] (CSP) where some of the [[constraint (mathematics)|constraint]]s can be violated (according to a violation degree) and in which [[preference]]s 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 [[loss function|cost function]]) among multiple possible solutions.

==Formal definition==

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

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

In WCSP, specific subclass of Valued CSP (VCSP),<ref>M C. Cooper, S de Givry, and T Schiex. Valued Constraint Satisfaction Problems, pages 185-207. Springer International Publishing, 2020.</ref>, costs are combined with the specific operator <math>\oplus</math> defined as:
:<math>\forall \alpha, \beta \in \langle 0,...,k \rangle, \alpha \oplus \beta = \min(k,\alpha+\beta)</math>.
The partial inverse of <math>\oplus</math> is <math>\ominus</math> defined by: if
:If <math>0 \le \beta \le \alpha < k</math>, <math> \alpha \ominus \beta = \alpha - \beta</math> and if <math>0 \le \beta <k</math>, <math>k \ominus \beta = k</math>.

Without any loss of generality, the existence of a nullary constraint <math>c_\empty</math> (a cost) as well as the presence of a unary constraint <math>c_x</math> for every variable <math>{{mvar|x</math>}} is assumed.

The total cost of a complete instantiation <math>I \in l(X)</math> is the bounded sum forof allthe softcost constraintof {{mvar|I}} on <math>c_S \in C</math> offor theall costsoft ofconstraint <math>I</math>c_S on\in <math>c_SC</math>, including the nullary cost <math>c_{\emptyset}</math> and the unary costs for <math>{{mvar|I</math>}} of the variables in <math>S</math>{{mvar|X}}.

Considering a WCN/CFN, the usual (NP-hard) task of WCSP is to find a complete instantiation with a minimal cost.

OherOther tasks in the related field of [[graphical model]] can be defined.<ref>M Cooper, S de Givry, and T Schiex. Graphical models: Queries, complexity, algorithms (tutorial). In 37th International Symposium on Theoretical Aspects of Computer Science (STACS-20), volume 154 of LIPIcs, pages 4:1-4:22, Montpellier, France, 2020.</ref>

==Resolution of binary/ternary WCSPs==

Line 27 ⟶ 30:

* Extend : cost transfer from unary constraint to constraint

[[File:TransfertsWCSP.pdf|thumb|800px|alt=Basic Equivalence Preserving Transformations|upright=5|center|Basic Equivalence Preserving Transformations.]]

The goal of Equivalence Preserving Transformations is to concentrate costs on the nullary constraint <math>c_{\empty}</math> and remove efficiently instantiations and values with a cost, added to <math>c_{\empty}</math>, that is greater than or equal to the forbidden cost or the cost of the best solution found so far. A branch-and-bound method is typically used to solve WCSPs, with lower bound <math>c_{\empty}</math> and upper bound <math>{{mvar|k</math>}}.

===Approach without cost transfer operations===

Line 41 ⟶ 44:

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 '''<math>GAC^{{sup|''w''}}-WSTR</math>''',<ref>C. Lecoutre, N. Paris, O. Roussel, S. Tabary. Propagating Soft Table Constraints. In Proceedings of CP’12, pages 390-405, 2012.</ref> 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''')<ref>C. Lecoutre. STR2: Optimized simple tabular reduction for table constraint. Constraints,

16(4):341–371, 2011.</ref> and cost transfer. Values that are no longer consistent with respect to GAC are identified and