Abstract
A number of data mining problems on probabilistic
networks can be modeled as Stochastic Constraint
Optimization and Satisfaction Problems, i.e., problems that involve objectives or constraints with a
stochastic component. Earlier methods for solving
these problems used Ordered Binary Decision Diagrams (OBDDs) to represent constraints on probability distributions, which were decomposed into
sets of smaller constraints and solved by Constraint
Programming (CP) or Mixed Integer Programming
(MIP) solvers. For the specific case of monotonic
distributions, we propose an alternative method:
a new propagator for a global OBDD-based constraint. We show that this propagator is (sub-)linear
in the size of the OBDD, and maintains domain
consistency. We experimentally evaluate the effectiveness of this global constraint in comparison
to existing decomposition-based approaches, and
show how this propagator can be used in combination with another data mining specific constraint
present in CP systems. As test cases we use problems from the data mining literature