Weighted Constraint Satisfaction with Set Variables

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Constraint Satisfaction and Satisfiability

Set variables are ubiquitous in modeling (soft) constraint problems, but efforts on practical consistency algorithms for Weighted Constraint Satisfaction Problems (WCSPs) have only been on integer variables. We adapt the classical notion of set bounds consistency for WCSPs, and propose efficient representation schemes for set variables and common unary, binary, and ternary set constraints, as well as cardinality constraints. Instead of reasoning consistency on an entire set variable directly, we propose local consistency check at the set element level, and demonstrate that this apparent "micro"-management of consistency does imply set bounds consistency at the variable level. In addition, we prove that our framework captures classical CSPs with set variables, and degenerates to the classical case when the weights in the problem contain only 0 and ⊤. Last but not least, we verify the feasibility and efficiency of our proposal with a prototype implementation, the efficiency of which is competitive against ILOG Solver on classical problems and orders of magnitude better than WCSP models using 0-1 variables to simulate set variables on soft problems.