Weighted Constraint Satisfaction with Set Variables

Abstract

Set variables are ubiquitous in modeling (soft) con-straint problems, but efforts on practical consistency al-gorithms for Weighted Constraint Satisfaction Problems (WCSPs) have only been on integer variables. We adapt the classical notion of set bounds consistency for WC-SPs, 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 di-rectly, we propose local consistency check at the set ele-ment level, and demonstrate that this apparent “micro”-management of consistency does imply set bounds con-sistency at the variable level. In addition, we prove that our framework captures classical CSPs with set vari-ables, 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 effi-ciency 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 vari-ables on soft problems.