Weighted constraint satisfaction with set variables
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited

Other information
AbstractSet 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 T. 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. Copyright © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
All Author(s) ListLee J.H.M., Sin C.F.K.
Name of Conference21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Start Date of Conference16/07/2006
End Date of Conference20/07/2006
Place of ConferenceBoston, MA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by American Association for Artificial Intelligence,
Year2006
Month11
Day13
Volume Number1
Pages80 - 85
ISBN1577352815
LanguagesEnglish-United Kingdom

Last updated on 2020-03-09 at 02:56