Stochastic Constraint Programming with And-Or Branch-and-Bound

Stochastic Constraint Programming with And-Or Branch-and-Bound

Behrouz Babaki, Tias Guns, Luc de Raedt

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 539-545. https://doi.org/10.24963/ijcai.2017/76

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 still lacks is support for the use of factorized probabilistic models that are popular in the graphical model community. We show how a state-of-the-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.
Keywords:
Constraints and Satisfiability: Solvers and Tools
Constraints and Satisfiability: Other approaches
Constraints and Satisfiability: Constraint Optimisation