Set domain propagation using ROBDDs

Abstract

Propagation based solvers typically represent variables by a current domain of possible values that may be part of a solution. Finite set variables have been considered impractical to represent as a domain of possible values since, for example, a set variable ranging over subsets of {1, . . . , N} has 2N possible values. Hence finite set variables are presently represented by a lower bound set and upper bound set, illustrating all values definitely in (and by negation) all values definitely out. Propagators for finite set variables implement set bounds propagation where these sets are further constrained. In this paper we show that it is possible to represent the domains of finite set variab..