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:
- 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.
- Integrated Probabilistic Inference: By embedding the ACE (Arithmetic Circuit) inference engine, the solver can efficiently query marginal probabilities for partial assignments, avoiding redundant computations.
- Advanced Bounding: Pruning is achieved through "Shallow Upper Bounds" (using interval arithmetic) and "Deep Upper Bounds" (look-ahead strategies).
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.
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