Content deleted Content added
m →Formal definition: \min |
m added VCSPs as something as which it is also known. Valued CSPs already redirects here, and in many of the sources of this article it is also called Valued CSP |
||
| (2 intermediate revisions by one other user 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==
Line 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
===Approach without cost transfer operations===
Line 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 '''
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
| |||