Article: Solving Set Constraint Satisfaction Problems using ROBDDs

[jai...@ptolemy.arc.nasa.gov]

JAIR is pleased to announce the publication of the following article:

Hawkins, P.J., Lagoon, V. and Stuckey, P.J. (2005)
"Solving Set Constraint Satisfaction Problems using ROBDDs",
Volume 24, pages 109-156.

For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/hawkins05a.html

Abstract:
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.

The article is available via:

-- comp.ai.jair.papers (also see comp.ai.jair.announce)

-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/hawkins05a.html

-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume24/hawkins05a.ps
The compressed PostScript file is named hawkins05a.ps.Z

For more information about JAIR, visit our WWW or FTP sites, or
contact jai...@isi.edu

--
Steven Minton
JAIR Managing Editor