Weighted constraint satisfaction problem: Difference between revisions

Revision as of 09:28, 18 November 2016

Revision as of 09:30, 18 November 2016

Line 19:

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> '''Existential 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:

Line 44:

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

==See also==