Weighted constraint satisfaction problem: Difference between revisions

Revision as of 02:25, 4 May 2016

Revision as of 21:33, 1 September 2016

Line 39:

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.

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 efficiently performing projection operations that are required to establish GAC.

==Benchmarks==