Weighted constraint satisfaction problem: Difference between revisions

Revision as of 22:10, 5 October 2014

Latest revision as of 13:49, 15 July 2024

(20 intermediate revisions by 8 users not shown)

Line 1:

WhereasIn all[[artificial constraintsintelligence]] in aand [[constraintoperations satisfaction problemresearch]], (CSP)a must'''Weighted beConstraint satisfiedSatisfaction Problem''' ('''WCSP'''), aalso known as '''WeightedValued Constraint Satisfaction Problem''' (WCSP'''VCSP'''), is a generalization of a [[constraint satisfaction problem]] (CSP) where constraintssome of the [[constraint (mathematics)|constraint]]s can be violated (according to a violation degree) and in which preferences[[preference]]s among solutions can be expressed. ManyThis realgeneralization problemsmakes canit bepossible representedto asrepresent Constraintmore Satisfactionreal-world Problem. Howeverproblems, ain wideparticular rangethose of problemsthat are over-constrained (no solution can be found without violating at least one constraint), or havethose multiplewhere solutionswe and the goal iswant to find the solution havinga minimal -cost solution (according to a [[loss function|cost function.]]) Thisamong kindmultiple ofpossible Constraint Satisfaction Problem are called Weighted Constraint Satisfaction Problem (WCSP)solutions.

==Formal definition==

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

AEach Weightedsoft Constraintconstraint Network<math>c_S (WCN)\in C</math> involves an ordered set {{mvar|S}} of variables, called its scope, and is defined as a tripletcost function from <math>l(S)</math> to <math> \langle X0,C...,k \rangle </math> where <math>Xl(S)</math> is a finitethe set of variables,possible instantiations of {{mvar|S}}. When an instantiation <math>CI \in l(S)</math> is agiven finitethe setcost of{{mvar|k}}, soft constraints andi.e., <math>c_S(I)=k>0</math>, it is eithersaid aforbidden. naturalOtherwise integerit oris <math>\infty</math>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:

Each soft constraint <math>c_S \in C</math> involves an ordered set <math>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> S </math>. When an instantiation <math>I \in l(S)</math> is given the cost <math>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).

:<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 <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 {{mvar|x}} is assumed.

In WCSP, specific subclass of Valued CSP (VCSP), 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 <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>.

WithoutThe anytotal loss of generality, the existencecost of a nullarycomplete constraintinstantiation <math>c_I \emptyin l(X)</math> (ais cost)the asbounded wellsum asof the presencecost of a{{mvar|I}} unaryon <math>c_S</math> for all soft constraint <math>c_xc_S \in C</math>, forincluding everythe variablenullary cost <math>xc_{\emptyset}</math> isand the unary costs for {{mvar|I}} of the variables in assumed{{mvar|X}}.

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

The total cost of an instantiation <math>I \in l(S)</math> on a soft constraint <math>c_S</math>, includes the cost of <math>I</math> on <math>c_S</math> as well as the nullary cost <math>c_{\emptyset}</math> and the unary costs for <math>I</math> of the variables in <math>S</math>.

Other 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>

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

== Resolution of binary/ternary WCSPs ==

=== Approach with cost transfer operations ===

== Resolution of binary/ternary WCSPs ==

=== 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

Systems, 134(3):311–342, 2003.</ref> '''ExistencialExistential Directional Arc consistency (EDAC)''',<ref>S. de Givry, F. Heras, M. Zytnicki, and J. Larrosa. Existential arc consistency: Getting closer

to full arc consistency in weighted CSPs. In Proceedings of IJCAI’05[[IJCAI]]’05, pages 84–89, 2005.</ref> '''Virtual Arc consistency (VAC)'''<ref>M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki. Virtual Arc Consistency for Weighted CSP. In Proceedings of AAAI’08[[AAAI]]’08, pages 253-258, 2008.</ref> and '''Optimal Soft Arc consistency (OSAC)'''.<ref>M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki, and T. Werner. Soft arc consistency revisited. Artificial Intelligence, 174(7-8):449–478, 2010.</ref>

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:

Algorithms enforcing such properties are based on Equivalence Preserving Transformations (EPTEPTs) 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

* 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, additionnedadded 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 {{mvar|k}}.

=== Approach without cost transfer operations ===

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.

Another more recent approach is based on super-reparametrizations<ref>T Dlask, T Werner, and S de Givry. Bounds on weighted CSPs using constraint propagation and super-reparametrizations. In Proc. of CP-21, Montpellier, France, 2021.</ref> which allows to relax the problem to compute tighter bounds.

== Resolution of n-ary WCSPs ==

== 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 '''<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 combinecombines 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 identifyidentified and

minimum costs of values are computed,. whichThis is particularly useful for performing 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.<ref>D Allouche, C Bessière, P Boizumault, S de Givry, P Gutierrez, J H.M. Lee, KL Leung, S Loudni, JP Métivier, T Schiex, and Y Wu. Tractability-preserving transformations of global cost functions. Artificial Intelligence, 238:166-189, 2016.</ref>

== Benchmarks ==

==Solvers==

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'''.

* '''https://www.ics.uci.edu/~dechter/software.html'''

* '''https://miat.inrae.fr/toulbar2''' (based on cost transfer operations)

== See also Benchmarks==

Many real-world WCSP benchmarks are available on '''http://genoweb.toulouse.inra.fr/~degivry/evalgm'''<ref>B Hurley, B O'Sullivan, D Allouche, G Katsirelos, T Schiex, M Zytnicki, S de Givry. Multi-Language Evaluation of Exact Solvers in Graphical Model Discrete Optimization. Constraints, 21(3):413-434, 2016.</ref> 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''').

==See also==

* [[Constraint satisfaction problem]]

* [[Constraint programming]]

* [[Preference-based planning]]

== References ==

{{Reflist}}

<references>

</references>

[[Category:Constraint programming]]