Abstract
Complex multi-stage decision making problems often involve uncertainty, for example, regarding demand or processing times. Stochastic constraint
programming was proposed as a way to formulate and solve such decision problems, involving
arbitrary constraints over both decision and random
variables. What stochastic constraint programming
currently lacks is support for the use of factorized
probabilistic models that are popular in the graphical model community. We show how a state-ofthe-art probabilistic inference engine can be integrated into standard constraint solvers. The resulting approach searches over the And-Or search tree
directly, and we investigate tight bounds on the expected utility objective. This significantly improves
search efficiency and outperforms scenario-based
methods that ground out the possible worlds