math.OCOct 13, 2026
SaveOptimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
Organizations: University of Calgary · University of Iowa
Abstract
Chance-constrained stochastic programs (CCSPs) require solutions that satisfy uncertain constraints with high probability. Standard approaches either embed scenarios directly into optimization by considering sample average approximation (SAA)-based reformulations, growing prohibitively expensive and often failing to find feasible solutions; or employ conservative reformulations that guarantee feasibility but sacrifice objective quality by design. We propose ACCESS (Adaptive Chance-Constrained Exploration via Structured Sampling), a structured sampling framework that decouples optimization from feasibility evaluation. First, high-quality candidate solutions are generated by solving many inexpensive single-scenario subproblems, avoiding sampling directly in the constrained high-dimensional solution space. Second, feasibility is assessed separately via large-scale batched simulation over a massive number of scenarios, which is naturally amenable to GPU parallelism. That reduces the search from a high-dimensional solution space to a two-dimensional parameter space controlling conservatism and scenario diversity; while concentrating on candidates near the feasibility boundary, where high-quality feasible solutions lie. We also introduce a variant, ACCESS(), which provides certified feasibility guarantees with probability . Experiments across three benchmark classes and five scenario distributions show that ACCESS matches or exceeds the best objective found by any method in nearly every setting, while ACCESS() is empirically feasible on every instance. The conservative reformulations remain several percent worse in objective, and SAA is frequently infeasible while taking an order of magnitude longer on the harder benchmarks.
Figures & tables
Figure 1: (a) Optimality gap versus feasibility rate on the largest knapsack instances at , one point per instance. Gap is relative to the best -feasible objective found by any method, so a solution that beats it while violating the chance constraint appears at a negative gap. GB and CVaR denote the Gaussian–Bonferroni and CVaR safe approximations, respectively; all baselines are introduced in Section 4 and Appendix B (b) Feasibility and optimality gap of candidates from random pairs and of the ACCESS candidates, on a single knapsack instance.
Figure 2: The ACCESS pipeline. (1) For each of the sampled scenarios, constrained BO searches over , in parallel on CPU. (2) The resulting candidates are scored against a set of validation scenarios in one batched GPU pass, and the best -feasible solution is returned.
| Small | Medium | Large | |||||||||||
| Method | Time | Time | Time | ||||||||||
| KP | SAA | 574 | 0.08% / 75% | 0.11% / 50% | 0.00% / 45% | 3588 | 0.21% / 40% | 0.19% / 25% | — / 0% | 3600 | 0.11% / 25% | 0.29% / 5% | — / 0% |
| CVaR | 2.5 | 5.82% / 100% | 4.88% / 100% | 3.33% / 100% | 7.3 | 4.16% / 100% | 3.40% / 100% | 1.37% / 85% | 156 | 3.25% / 100% | 2.45% / 100% | 0.89% / 35% | |
| GB | 0.1 | 3.52% / 100% | 2.94% / 100% | 2.54% / 100% | 1.5 | 3.00% / 100% | 2.65% / 100% | 2.14% / 100% | 111 | 2.87% / 100% | 2.51% / 100% | 2.05% / 100% | |
| ACCESS | 88 | 0.00% / 100% | 0.01% / 100% | 0.00% / 100% | 111 | 0.00% / 95% | 0.04% / 100% | 0.00% / 100% | 129 | 0.01% / 100% | 0.01% / 90% | 0.00% / 95% | |
| ACCESS( ) | 88 | 0.07% / 100% | 0.10% / 100% | 0.50% / 100% | 111 | 0.06% / 100% | 0.11% / 100% | 0.39% / 100% | 129 | 0.03% / 100% | 0.05% / 100% | 0.27% / 100% | |
Table 1: Feasibility, objective, and runtime results. Each cell reports FO-gap / -feasibility rate, followed by runtime in seconds (averaged over values). FO-gap is relative to BKO (Best Known Objective): the best -feasible objective across all methods per instance. SAA and CVaR use scenarios; ACCESS( ) applies Hoeffding correction with . Sizes: KP: , ; MWM: , ; SRCSP: , . Each entry is averaged over 20 test instances.
Figure 3: Feasibility rate vs. optimality gap under non-Gaussian distributions, on KP with . Each point is one of 20 instances, and the dashed line marks . SAA and CVaR use . Gap is relative to the best -feasible objective, so infeasible solutions may have negative gaps.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | Empirical | Hoeffding lower bound | |
|---|---|---|---|
| SAA-favorable ( , ) | 1,000 | 0.99 | 0.951 |
| ACCESS ( , ) | 1,000,000 | 0.99 | 0.988 |
Table 2: Hoeffding lower bounds on true feasibility for an observed empirical rate of , with .
| Parameter | Value | Description |
| Scenario Sampling | ||
| 1000 | Scenarios drawn from the problem’s own distribution | |
| Bayesian Optimization (per scenario) | ||
| 5 | Initial Sobol samples | |
| 10 | BO iterations after initialization | |
| Acquisition | qLogEI | Log expected improvement, feasibility-constrained |
Table 3: ACCESS hyperparameter settings used in all experiments.
Figure 4: Improvements based on the number of BO iterations. Rows are benchmarks and columns are instance sizes. Iteration 0 is the end of the initial design, so the curve starts at 0% by construction. Shaded regions are the standard error across the 20 instances.
Figure 5: FO-gap vs. number of candidates (log scale). Rows correspond to benchmarks (KP, MWM, SRCSP) and columns to instance sizes (Small, Medium, Large). FO-gap is computed relative to the best FO at . Higher (red) generally requires more candidates to achieve low FO-gap. Shaded regions show standard error across 20 test instances.
Figure 6: Selected parameters per instance. Each point represents one test instance; colors denote . Rows correspond to benchmarks and columns to instance sizes.
| Method | ||||
|---|---|---|---|---|
| hom_20 | SAA (S=1k) | 0.21% / 40% | 0.19% / 25% | — / 0% |
| SAA (S=10k) | 0.12% / 90% | 0.04% / 75% | 0.03% / 30% | |
| CVaR (S=1k) | 4.16% / 100% | 3.40% / 100% | 1.37% / 85% | |
| CVaR (S=10k) | 4.51% / 100% | 4.02% / 100% | 3.12% / 100% | |
| GB | 3.00% / 100% | 2.65% / 100% | 2.14% / 100% | |
| ACCESS (scalar ) | 0.00% / 95% | 0.04% / 100% | 0.00% / 100% |
Table 4: Heterogeneous uncertainty on the knapsack benchmark ( , ). Each cell reports FO-gap / -feas rate over 20 seeds, with feasibility measured on held-out scenarios. The four settings share instances and seeds and differ only in the per-row ; hom_20 is Medium KP from the main results.
| , | , | ||||||
|---|---|---|---|---|---|---|---|
| Method | |||||||
| Student- | SAA (S=1k) | 0.13% / 40% | 0.15% / 25% | — / 0% | 0.00% / 10% | — / 0% | — / 0% |
| SAA (S=10k) | 0.44% / 80% | 0.12% / 55% | 0.03% / 40% | 0.35% / 95% | 0.06% / 70% | 0.02% / 25% | |
| CVaR (S=1k) | 5.24% / 100% | 4.77% / 100% | 2.84% / 50% | 3.86% / 100% | 3.09% / 100% | 1.19% / 20% | |
| CVaR (S=10k) | 6.31% / 100% | 6.71% / 100% | 7.80% / 100% | 5.23% / 100% | 5.43% / 100% | 4.88% / 100% | |
| ACCESS | 0.00% / 100% | 0.01% / 100% | 0.00% / 90% | 0.00% / 100% | 0.03% / 95% | 0.02% / 85% | |
Table 5: Non-Gaussian uncertainty on the knapsack benchmark. Each cell reports FO-gap / -feas rate over 20 seeds, with feasibility measured on held-out scenarios from the same distribution.
| Small | Medium | Large | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Method | ||||||||||
| KP | ACCESS | 0.00 | 0.01 | 0.00 | 0.00 | 0.04 | 0.00 | 0.01 | 0.01 | 0.00 |
| 0.09 | 0.18 | 0.11 | 0.19 | 0.28 | 0.26 | 0.34 | 0.33 | 0.37 | ||
| +0.09 | +0.17 | +0.11 | +0.20 | +0.24 | +0.26 | +0.33 | +0.33 | +0.37 | ||
| MWM | ACCESS | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 0.19 | 0.17 | 0.43 | 0.35 | 0.21 | 0.73 | 0.26 | 0.39 | 0.66 | ||
Table 6: Ablation: ACCESS vs. the nominal-only ( ) variant, both under the uncertified rule. Rows report FO-gap (%) against BKO; is the mean paired objective difference (positive ACCESS ahead).
| Benchmark | Instances | Mean gain | Win | Tie | Loss |
|---|---|---|---|---|---|
| KP | 180 | +0.23% | 114 | 65 | 1 |
| MWM | 180 | +0.38% | 67 | 113 | 0 |
| SRCSP | 180 | +0.03% | 5 | 174 | 1 |
| Student- | 120 | +0.38% | 104 | 14 | 2 |
| Jump | 120 | +0.72% | 117 | 3 | 0 |
| Clustered | 120 | +0.81% | 110 | 4 | 6 |
Table 7: Mean paired objective gain of ACCESS over the nominal-only ( ) variant, both under the uncertified rule. Win, tie and loss count the instances on which ACCESS is ahead, equal and behind.
| Small | Medium | Large | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| KP | 10 | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% |
| 100 | 0.14% / 20% | 0.00% / 10% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | |
| 1000 | 0.08% / 75% | 0.11% / 50% | 0.00% / 45% | 0.21% / 40% | 0.19% / 25% | — / 0% | 0.11% / 25% | 0.29% / 5% | — / 0% | |
| 10000 | 0.10% / 85% | 0.10% / 70% | 0.04% / 80% | 0.12% / 90% | 0.04% / 75% | 0.03% / 30% | 0.19% / 95% | 0.14% / 70% | 0.06% / 30% | |
| MWM | 10 | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% |
Table 8: SAA results varying sample size . Each cell reports FO-gap / -feas rate. Time limit: 3600 s.
| Small | Medium | Large | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| KP | 10 | — / 0% | — / 0% | — / 0% | 0.00% / 5% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% |
| 100 | 4.13% / 100% | 2.59% / 80% | 0.00% / 5% | 2.47% / 90% | 1.52% / 30% | — / 0% | 1.33% / 60% | — / 0% | — / 0% | |
| 1000 | 5.82% / 100% | 4.88% / 100% | 3.33% / 100% | 4.16% / 100% | 3.40% / 100% | 1.37% / 85% | 3.25% / 100% | 2.45% / 100% | 0.89% / 35% | |
| 10000 | 6.00% / 100% | 5.26% / 100% | 4.39% / 100% | 4.51% / 100% | 4.02% / 100% | 3.12% / 100% | 3.81% / 100% | 3.34% / 100% | 2.38% / 100% | |
| MWM | 10 | 0.00% / 10% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% | — / 0% |
Table 9: CVaR results varying sample size . Each cell reports FO-gap / -feas rate. Time limit: 3600 s.
Figure 7: Per-instance feasibility rate versus optimality gap for the Knapsack Problem (KP). Each point is one of the 20 instances, feasible or not.
Figure 8: Per-instance feasibility rate versus optimality gap for Maximum Weight Matching (MWM).
Figure 9: Per-instance feasibility rate versus optimality gap for Stochastic Resource-Constrained Shortest Path (SRCSP).
Figure 10: Generation time versus FO-gap for KP, over the -feasible solutions only.
Figure 11: Generation time versus FO-gap for MWM, over the -feasible solutions only.
Figure 12: Generation time versus FO-gap for SRCSP, over the -feasible solutions only.
Figure 13: Feasibility distributions for Knapsack (KP). Rows are instance sizes and columns are .
Figure 14: Feasibility distributions for Maximum Weight Matching (MWM).
Figure 15: Feasibility distributions for Stochastic Resource-Constrained Shortest Path (SRCSP).
| Small | Medium | Large | ||||||||
| Method | ||||||||||
| KP | ACCESS | 87.3/2.7 | 85.7/2.8 | 81.6/2.8 | 111.1/2.7 | 109.8/2.8 | 103.2/2.8 | 122.9/16.1 | 109.6/15.9 | 106.0/15.8 |
| SAA | 1082 | 440 | 199 | 3601 | 3601 | 3561 | 3600 | 3600 | 3600 | |
| GB | 0.1 | 0.1 | 0.1 | 1.3 | 1.6 | 1.7 | 58 | 8.6 | 267 | |
| CVaR | 3.5 | 2.3 | 1.6 | 6.3 | 6.6 | 9.1 | 81 | 130 | 256 | |
| MWM | ACCESS | 131.3/6.7 | 130.7/6.4 | 127.0/6.7 | 281.6/15.3 | 276.5/14.8 | 271.3/14.4 | 526.7/22.9 | 543.2/23.6 | 557.3/22.4 |
Table 10: Generation time in seconds (mean across 20 instances). ACCESS times shown as generation/feasibility.
More in this topic
Chance-Constrained Optimization
Chance-constrained optimization chooses decisions that optimize performance while limiting the probability of violating uncertain constraints.
See all 29 papers