Constraint programming is a state of the art technique
for learning the structure of Bayesian Networks from data
(Bayesian Network Structure Learning – BNSL). However,
scalability both for CP and other combinatorial optimization
techniques for this problem is limited by the fact that the ba-
sic decision variables are set variables with domain sizes that
may grow super polynomially with the number of random
variables. Usual techniques for handling set variables in CP
are not useful, as they lead to poor bounds. In this paper, we
propose using decision trees as a data structure for storing sets
of sets to represent set variable domains. We show that rela-
tively simple operations are sufficient to implement all propa-
gation and bounding algorithms, and that the use of these data
structures improves scalability of a state of the art CP-based
solver for BNSL