Compiling and Executing Disjunctions of Finite Domain Constraints
Björn Carlson, Mats Carlsson · The MIT Press eBooks · 1995
We present two schemes for compiling disjunctions of finite domain constraints, where disjunction is treated as constructive. In the first scheme each disjunction is compiled to a set of indexicals, i.e. a set of range functions computing domain restrictions, such that the evaluation of the indexicals maintains a weak form of consistency of the disjunction. The second scheme is based on constraint lifting, i.e. constructive disjunction applied to the set of constraint stores given by executing a disjunction of goals, for which we provide an algorithm for lifting finite domain constraints. This scheme maintains stronger consistency than the first with a penalty in efficiency. We compare the two schemes with speculative disjunction, i.e. disjunction executed nondeterministically, and with disjunction via cardinality. Our conclusions are that the indexical scheme implements the most efficient pruning for many disjunctive constraints, such as resource and maximum/minimum constraints, and that the lifting scheme can be used for implementing lookahead pruning.