Stronger Consistencies in WCSPs with Set Variables

Lee and Siu made possible for the first time modeling and reasoning with set variables in weighted constraint satisfaction problems (WCSPs). In addition to an efficient set variable representation scheme, they also defined the notion of set bounds consistency, which is generalized from NC* and AC* for integer variables in WCSPs, and their associated enforcement algorithms. In this paper, we adapt ideas from FDAC and EDAC for integer variables to achieve stronger consistency notions for set variables. The generalization is non-trivial due to the common occurrence of ternary set constraints. Enforcement algorithms for the new consistencies are proposed. Empirical results confirm the feasibility and efficiency of our proposal.