Representing Uncertainty in Stochastic Programming Using SPNs

Optimization under uncertainty is often made tractable by sampling: expectations and chance constraints are replaced by sample-average counterparts via scenario expansion, where meeting stronger statistical requirements may require larger samples and more sophisticated optimization methods. We take a different route and represent uncertainty using a tractable probabilistic model (TPM), specifically a sum-product network learned from data. Its structural properties (smoothness, decomposability) enable exact marginal inference under the fitted model, allowing us to construct conditional probability queries for constraint violations that depend on the decision variables. We represent these queries using refinable piecewise-linear approximations that admit explicit mixed-integer linear formulations. A learned chance constraint thus becomes part of the optimization problem itself, without explicit scenario expansion: for a fixed circuit architecture and encoding policy, additional training observations do not introduce individual optimization attachments. We evaluate the approach on the well-known newsvendor problem and a stochastic knapsack problem, examining how learning and encoding errors affect decision quality and computational cost. The resulting decisions are evaluated for feasibility under the compiled learned constraint and independently assessed against the uncertainty distribution.