Computer Science – Artificial Intelligence
Scientific paper
2011-09-09
Journal Of Artificial Intelligence Research, Volume 24, pages 109-156, 2005
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.1638
In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.
Hawkins P. J.
Lagoon Vitaly
Stuckey Peter J.
No associations
LandOfFree
Solving Set Constraint Satisfaction Problems using ROBDDs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving Set Constraint Satisfaction Problems using ROBDDs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Set Constraint Satisfaction Problems using ROBDDs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-38062