Weighted constraint satisfaction problem: Difference between revisions

Revision as of 17:25, 12 September 2015

Revision as of 16:36, 2 April 2016

Line 36:

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