Content deleted Content added
No edit summary |
|||
Line 1:
Whereas all constraints in a [[constraint satisfaction problem]] (CSP) must be satisfied, a '''Weighted Constraint Satisfaction Problem''' ('''WCSP''') is a constraint satisfaction problem where constraints can be violated (according a violation degree) and in which preferences among solutions can be expressed. Many real problems can be represented as Constraint Satisfaction Problem. However, a wide range of problems are over-constrained (no solution can be found without violating at least one constraint) or have multiple solutions and the goal is to find the solution having minimal cost according to a cost function. This kind of Constraint Satisfaction Problem are called Weighted Constraint Satisfaction Problem (WCSP).
==Formal definition==
A Weighted Constraint Network (WCN) is a triplet <math>\langle X,C,k \rangle</math> where <math>X</math> is a finite set of variables, <math>C</math> is a finite set of soft constraints and <math>k>0</math> is either a natural integer or <math>\infty</math>.
Line 15 ⟶ 14:
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)''',<ref>M. Cooper. Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and
Line 25 ⟶ 22:
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:
* Project : cost transfer from constraints to unary constraints
* ProjectUnary : cost transfer from unary constraint to nullary constraint
Line 34 ⟶ 30:
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, additionned to <math>c_{\empty}</math>, that is greater than or equal to the forbidden cost or the cost of the best solution found
===
An alternative to cost transfer algorithms is the algorithm '''PFC-MRDAC'''<ref>E.C. Freuder and R.J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58(1-
3):21–70, 1992.</ref> which is a classical branch and bound algorithm that computes lower bound <math>lb</math> at each node of the search tree, that corresponds to an under-estimation of the cost of any solution that can be obtained from this node. The cost of the best solution found is <math>ub</math>. When <math>lb \geq ub</math>, then the search tree from this node is pruned.
==
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.
Line 48 ⟶ 43:
minimum costs of values are computed, which is particularly useful for performing efficiently projection operations that are required to establish GAC.
==
Many real-world WCSP benchmarks are available on '''http://costfunction.org/en/benchmark'''<ref>The aims of this web site is to promote cost function network in providing Benchmark and teaching material, solver demo, link to articule about cost function used in the contexte of constraint programming.</ref> and on '''http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html'''.
==
* [[Constraint satisfaction problem]]
* [[Constraint programming]]
* [[Preference-based planning]]
==
{{Reflist}}
[[Category:Constraint programming]]
| |||