A number of data mining problems on probabilistic networks can be modelled as Stochastic Constraint Optimisation 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 speci c case of monotonic distributions, we propose an alternative method: a new propagator for a global OBDD-based constraint. We show that this propagator is efcient and maintains domain consistency. We experimentally evaluate this global constraint in comparison to existing decomposition-based approaches. As test cases we use problems from the data mining literature.
Consider the following example of a viral marketing problem [
SCPMDs like this one are NP-hard because they involve two computationally
expensive tasks. We need perform probabilistic inference, which can be reduced
to a #P-complete counting problem [
The rst contribution of this work is that we show that some relations between variables are lost in the decomposition process. Consequently, this method prunes the search space inadequately and thus lacks e ciency. Speci cally, it does not guarantee generalised arc consistency (GAC).
As our second contribution we address this aw by introducing a global
constraint for SCOPs whose underlying probability distributions are monotonic.
We propose a constraint propagation algorithm for this stochastic constraint on
monotonic distributions (SCMD), which preserves relations between variables
and guarantees GAC. As in our earlier approach, we represent the probability
distributions as OBDDs. We use the concept of derivatives of propositional
formulas [
We demonstrate the e ectiveness of this method by evaluating the running time of our new algorithm on problems from the datamining literature, comparing its performance to that of our earlier CP-based and MIP-based methods. In these experiments, our new approach outperforms the CP method, and performs complementory to the MIP method. However: the running times of our new, global constraint scale much better with problem size than this MIP method.