Learning Chance-Constrained Bounds
Chance-constrained problems require constraints to hold with high probability rather than deterministically. Sampling scenarios from observations turns this stochastic problem into a deterministic one, which is easier to solve. We propose a general approach to solve any combinatorial chance-constrained problem with branch and bound. In our algorithm, bounds are derived from a Lagrangian decomposition over the scenarios, typically tightened through a sub-gradient ascent. We replace this expensive optimization with a graph neural network that predicts the multipliers in a single forward pass, trained self-supervised on the bound it induces, which remains valid regardless of the precision of the GNN. On the chance-constrained multi-dimensional knapsack: about 10× fewer explored nodes and up to 2× faster solving on the largest instances vs. a constraint-programming baseline.