Abstract
In stochastic optimization, ensuring that complex combinatorial constraints are satisfied with a specific probability threshold—known as a confidence or chance constraint—is a significant challenge. This paper introduces a generalized framework that utilizes Multi-valued Decision Diagrams (MDDs) to provide an exact filtering algorithm for such constraints. By mapping probability mass functions directly onto MDD arcs, the proposed method moves beyond the limitations of previous binary inequality-based approaches, offering a robust and efficient solution for a wide range of combinatorial models.
Introduction
Robust optimization aims to find solutions that remain valid under uncertainty, such as fluctuating demand or transit times. A common approach is the use of "Confidence constraints," which ensure that the probability of a solution's validity meets a minimum threshold $\gamma$. While Constraint Programming (CP) is powerful for deterministic problems, it has historically lacked a generic mechanism to enforce confidence levels for complex, non-linear constraints. Previous state-of-the-art methods were restricted to simple algebraic structures like binary inequalities. This work addresses this gap by leveraging MDDs to apply confidence thresholds to any constraint representable in a combinatorial model.
Methodology
The core of the proposed framework is the use of Multi-valued Decision Diagrams (MDDs), directed acyclic graphs that represent the set of all valid assignments for a given constraint.
MDD Representation
The authors leverage MDDs as a foundational structure for representing combinatorial constraints. By expanding the state space within the MDD, complex logic can be encoded efficiently.
Probability Integration and Filtering
The authors integrate uncertainty by mapping the probability mass functions (PMFs) of random variables directly onto the arcs of the MDD. This transformation allows the MDD to function as a probability calculator over massive combinatorial spaces.
A linear-time algorithm performs forward and backward passes through the MDD to calculate the cumulative probability of reaching a successful "True" state ($tt$). If a decision variable choice leads to a state where the maximum possible remaining probability falls below the threshold $\gamma$, that choice is pruned from the search space. To address potential "state explosion," the authors also introduced specialized propagators (Confidence$_{\to}$, Confidence$_{\in}$, and Confidence$_{\le}$) for lighter filtering in common scenarios.
Experimental Evaluation
The framework was evaluated using a Chemical Deliveries Assignment Problem, where a factory must assign deliveries of uncertain quantities to containers with fixed capacities. The study utilized two datasets (small and large) with delivery counts ranging from 40 to 100.
Key Results
- Precision and Robustness: The MDD-based method correctly identified unsatisfiable instances that previous methods incorrectly flagged as valid, demonstrating superior precision in enforcing confidence levels.
- Computational Efficiency: MDD construction and filtering were highly efficient, typically taking only a few milliseconds for test cases with approximately 1,000 nodes and 6,000 arcs.
- Global Confidence: Treating groups of constraints as a single "Global Confidence Constraint" proved more effective than individual checks, as it correctly accounts for probability interactions.
Conclusion
This paper presents a significant advancement in stochastic constraint programming. By using MDDs as a foundational structure for probability summation, the authors provide a versatile and exact method for handling generalized confidence constraints. Future work will focus on scaling these techniques to even larger industrial problems and exploring more complex dependencies between random variables, such as Markov chains.
Summary updated