Weighted constraint satisfaction problem: Difference between revisions

Revision as of 16:11, 10 September 2015

Revision as of 17:25, 12 September 2015

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