Utilisateur:NparisCRIL/Bac a sable

Formal definition[modifier | modifier le code]

A Weighted Constraint Network (WCN) is a triplet $\langle X,C,k\rangle$ where $X$ is a finite set of variables, $C$ is a finite set of soft constraints and $K$ >0 is either a natural integer or $\infty$ .

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

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

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

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[modifier | modifier le code]

Approach with cost transfer operations[modifier | modifier le code]

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)^[1], Existencial Directional Arc consistency (EDAC)^[2], Virtual Arc consistency (VAC)^[3] and Optimal Soft Arc consistency (OSAC)^[4].

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
Extend : cost transfer from unary constraint to constraint

Basic Equivalence Preserving Transformations.

The goal of Equivalence Preserving Transformations is to concentrate costs on the nullary constraint $c_{\emptyset }$ and remove efficiently instantiations and values with a cost, additionned to $c_{\emptyset }$ , that is greater or equal than the forbidden cost or the cost of the best solution found.

Approach without cost transfer operations[modifier | modifier le code]

An alternativ to cost transfer algorithms is the algorithm PFC-MRDAC^[5] wich is a classical branch and bound algorithm that computs lower bound $lb$ 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 $ub$ . When $lb\geq ub$ , then the search tree from this node is pruned.

Resolution of n-ary WCSPs[modifier | modifier le code]

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 $GAC^{w}-WSTR$ ^[6], 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 combine two techniques, namely, Simple Tabular Reduction (STR)^[7] and cost transfer. Due to analyse of valid and invalid instantiations, values that are no longer consistent with respect to GAC are identify and minimum costs of values are computed that is particularly useful to performing efficiently projection operations that are required to establish GAC.

Benchmarks[modifier | modifier le code]

Many real-world WCSP benchmarks are available on http://costfunction.org/en/benchmark^[8] and on http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.

References[modifier | modifier le code]

↑ M. Cooper. Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, 134(3):311–342, 2003.
↑ 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, pages 84–89, 2005.
↑ M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki. Virtual Arc Consistency for Weighted CSP. In Proceedings of AAAI’08, pages 253-258, 2008.
↑ 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.
↑ E.C. Freuder and R.J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58(1- 3):21–70, 1992.
↑ C. Lecoutre, N. Paris, O. Roussel, S. Tabary. Propagating Soft Table Constraints. In Proceedings of CP’12, pages 390-405, 2012.
↑ C. Lecoutre. STR2: Optimized simple tabular reduction for table constraint. Constraints, 16(4):341–371, 2011.
↑ 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.

[1] M. Cooper. Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets and Systems, 134(3):311–342, 2003.

[2] 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, pages 84–89, 2005.

[3] M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki. Virtual Arc Consistency for Weighted CSP. In Proceedings of AAAI’08, pages 253-258, 2008.

[4] 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.

[5] E.C. Freuder and R.J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58(1- 3):21–70, 1992.

[6] C. Lecoutre, N. Paris, O. Roussel, S. Tabary. Propagating Soft Table Constraints. In Proceedings of CP’12, pages 390-405, 2012.

[7] C. Lecoutre. STR2: Optimized simple tabular reduction for table constraint. Constraints, 16(4):341–371, 2011.

[8] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]