Weighted constraint satisfaction problem: Difference between revisions

Revision as of 16:36, 2 April 2016

Revision as of 02:25, 4 May 2016

Line 18:

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

Line 28:

[[File:TransfertsWCSP.pdf|thumb|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.

===Approach without cost transfer operations===

Line 41:

This algorithm combine 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 identify and

minimum costs of values are computed, which is particularly useful for performing efficiently performing projection operations that are required to establish GAC.

==Benchmarks==

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 articulearticle about cost function used in the contexte of constraint programming.</ref> and on '''http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html'''.

==See also==