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

Behrouz Babaki, Tias Guns, Luc De Raedt

Introduction

Stochastic Constraint Programming (SCP) provides a robust framework for decision-making under uncertainty, yet it often suffers from exponential complexity when modeled via traditional scenario-based approaches. This paper introduces a novel solution: integrating factorized probabilistic models, such as Bayesian Networks, directly into constraint solvers using an And-Or Branch-and-Bound (AOB&B) search. By exploiting problem structure and employing advanced bounding techniques, this approach significantly outperforms methods that rely on exhaustive scenario grounding.

Methodology

The proposed framework for Factored Stochastic Constraint Problems (FSCP) is built upon three primary components:

  1. And-Or Search Structure: Unlike flat search trees, this model utilizes OR nodes for decision points and AND nodes for random variables. This structure naturally mirrors the conditional independence found in factorized models.
  2. Integrated Probabilistic Inference: By embedding the ACE (Arithmetic Circuit) inference engine, the solver can efficiently query marginal probabilities for partial assignments, avoiding redundant computations.
  3. Advanced Bounding: Pruning is achieved through "Shallow Upper Bounds" (using interval arithmetic) and "Deep Upper Bounds" (look-ahead strategies).
And-Or search tree and associated factorized probabilistic model.

A key insight is that pruning can occur at both OR and AND nodes. If the maximum possible utility of a random variable's remaining branches cannot improve the parent node's value, exploration of those branches is terminated. The authors implemented these components as modular extensions to the Gecode constraint solver, enabling the handling of complex, non-linear constraints.

Experimental Evaluation

The methodology was evaluated on two stochastic optimization benchmarks: the Stochastic Knapsack problem (where weights and costs depend on a hidden state modeled by a Hidden Markov Model) and the Stochastic Investment problem. The "Native" AOB&B approach was compared against scenario-based versions using standard Constraint Programming (CP) and high-performance Mixed-Integer Programming (MIP) solvers like Gurobi.

Key Results

The AOB&B method demonstrated superior scalability, successfully solving 7-stage problems where traditional solvers encountered memory or time limits. On a 6-stage knapsack instance, AOB&B was approximately 1.5x faster than the leading MIP solver and orders of magnitude faster than standard CP.

Runtime performance and search space reduction across varying problem capacities.

As shown in the results, the application of bounds leads to a massive reduction in the search space. In specific knapsack instances, the number of failures was reduced from millions to zero, highlighting the efficiency of the integrated bounding logic. The data suggests that while deeper bounds require more time per node, the resulting reduction in total nodes visited leads to a significant net gain in performance.

Conclusion

This research demonstrates that treating probability distributions as factorized models allows solvers to exploit independence and avoid redundant work. While highly effective, the current model assumes decisions do not influence the underlying probability distributions. Future research could extend this to "global chance constraints" or approximate methods for even larger-scale problems where low-probability branches might be safely ignored.

Summary updated

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 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.
BibTeX
@inproceedings{babaki2017stochastic,
  author = {Behrouz Babaki and Tias Guns and Luc De Raedt},
  title = {{Stochastic Constraint Programming with And-Or Branch-and-Bound}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/76},
}
Figure