PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs

Justin Dumouchelle, Shunyu Yao, Beste Basciftci, Thiago Serra

arXiv:2610.19027v1math.OCcs.LG

TL;DR

Chance-constrained programs require uncertain constraints to hold with high probability, but SAA can be prohibitively expensive and safe approximations can sacrifice objective quality. ACCESS searches parameterized single-scenario subproblems and evaluates feasibility separately; across benchmarks, it reports near-best feasible objectives, with ACCESS(δ) providing a feasibility guarantee.

  • Problem

    Chance-constrained programs require solutions to satisfy uncertain constraints with high probability, while SAA can become intractable for combinatorial problems and safe approximations can yield suboptimal solutions.

    Source: §1 · p. 1

  • Method

    ACCESS generates candidates by solving single-scenario subproblems indexed by conservatism γ and scenario magnitude β, then separately evaluates them on a large validation set.

    Source: §1 · p. 2

  • Results

    Across knapsack, matching, and shortest-path benchmarks under five distributions, ACCESS and ACCESS(δ) return α-feasible solutions at worst-case mean gaps of 0.04% and 0.64%, respectively.

    Source: §1 · p. 3

  • Takeaways & Limitations

    ACCESS finds high-quality α-feasible solutions across the reported benchmarks, while ACCESS(δ) provides a certified feasibility guarantee with probability 1−δ.

    Source: §5 · p. 9

    ACCESS presumes cheap deterministic subproblems and benefits heavily from parallel hardware; its guarantee concerns feasibility, not objective value.

    Source: §4 · p. 9

Abstract

from arXiv · show

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($\delta$), which provides certified feasibility guarantees with probability $1-\delta$. 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($\delta$) 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.

1 INTRODUCTION

Chance-constrained programs are hard to solve because feasibility is expensive to evaluate, especially for combinatorial decisions. ACCESS separates candidate generation from feasibility evaluation and searches a two-parameter space; experiments report near-best feasible objectives and a certified variant.

1 INTRODUCTION

  • SAA can require thousands of scenarios to assess 99th-percentile constraints, making its MILP intractable for practical combinatorial problems; safe approximations guarantee feasibility but can sacrifice objective quality.Both approaches are single-shot methods that produce one solution.Source: §1 · pp. 1–2
  • ACCESS solves inexpensive single-scenario subproblems parameterized by conservatism γ and scenario magnitude β, then evaluates candidates separately over a large validation set.Bayesian Optimization searches the two-dimensional parameter space to concentrate candidates near the feasibility boundary; subproblems run in parallel on CPUs and validation can run on GPUs.Source: §1 · p. 2
  • On the largest knapsack instances, ACCESS bridges the objective–feasibility trade-off between SAA and conservative methods, concentrating its search near α-feasible candidates.Random (γ, β) pairs trace the feasibility–quality trade-off; ACCESS focuses on candidates where it meets α-feasibility.Source: §1 · p. 2, Figure 1 · p. 2
  • ACCESS(δ) returns an α-feasible solution with probability at least 1−δ for any distribution that can be sampled.The guarantee is obtained by moving feasibility certification to the selection step, separate from candidate generation.Source: §1 · pp. 2–3
  • Across knapsack, matching, and shortest-path benchmarks under five distributions, ACCESS and ACCESS(δ) return α-feasible solutions at worst-case mean gaps of 0.04% and 0.64%, respectively.The reported gaps are relative to the best objective found by any method.Source: §1 · p. 3

2 PRELIMINARIES

The preliminaries define chance-constrained programs and explain how SAA, safe approximations, and empirical scenario evaluation handle feasibility. Related work includes conservative approximations, sampling-based optimization, and learned constraint models; ACCESS instead searches for boundary-focused candidates.

2.1 CHANCE-CONSTRAINED STOCHASTIC PROGRAMS

  • A chance-constrained program optimizes over a deterministic feasible set while requiring uncertain constraints to hold with confidence α; this paper focuses mainly on linear constraints and covers individual and joint constraints.The decision set may include integer and continuous variables, and the paper considers knapsack, matching, and routing examples.Source: §2.1 · p. 3
  • SAA estimates the chance constraint using sampled scenarios and, for the linear models considered, can be reformulated as an equivalent MILP requiring satisfaction in at least ⌈α|S|⌉ scenarios.Feasibility is assessed empirically on a separate scenario set T, analogous to using training and test sets.Source: §2.1 · pp. 3–4
  • Safe approximations impose deterministic sufficient conditions that ensure feasibility but may exclude feasible solutions of the original problem, affecting solution quality.The paper uses Gaussian–Bonferroni and CVaR as benchmark approximations.Source: §2.1 · p. 3

2.2 RELATED WORK

  • Prior optimization methods use conservative approximations or SAA with fixed conservatism, while ACCESS makes conservatism searchable and samples the scenarios defining its subproblems.Earlier margin-search approaches return a single solution, whereas ACCESS samples subproblem scenarios and certifies the selected candidate.Source: §2.2 · p. 4
  • Sampling-based learning methods generate diverse combinatorial candidates with constraint penalties, while constraint-learning approaches embed predictive models; ACCESS instead generates boundary-focused candidates without an embedded surrogate or active data collection.The cited learning-based methods target settings where the MILP solver is itself the bottleneck; the paper says random solutions rarely fall near the feasibility boundary.Source: §2.2 · p. 4

3 METHODOLOGY

ACCESS separates optimization from feasibility evaluation by searching parameterized single-scenario subproblems, then selecting candidates using independent validation scenarios. Bayesian Optimization steers the search, GPU batching scales evaluation, and a raised selection threshold yields a feasibility guarantee.

3 METHODOLOGY

  • ACCESS replaces one analytically tightened problem with empirical search over subproblems of varying conservatism γ and diversity β.The pipeline generates candidates and assesses their feasibility in a separate validation stage.Source: §3 · p. 4, Figure 2 · p. 5

3.1 PARAMETERIZED SUBPROBLEMS

  • Single-scenario solves are cheap but tailored to their sampled realization, so binding constraints can make their solutions violate the chance constraint.ACCESS balances this issue against safe approximations, which can be excessively conservative; it uses an empirical tightening parameter γ and a linearized margin under nonnegative data and decisions.Source: §3.1 · p. 5
  • The diversification parameter β interpolates constraints between nominal data at β=0 and realized-scenario data at β=1, while γ controls conservatism.Searching (γ, β) leaves the combinatorial structure to the solver and concentrates candidates near the feasibility boundary.Source: §3.1 · p. 6

3.2 STRUCTURED SAMPLING VIA BAYESIAN OPTIMIZATION

  • For each of N sampled scenarios, ACCESS searches (γ, β) with constrained Bayesian Optimization, scoring within-search candidates on V′ and reserving independent V for final selection.The search maximizes the subproblem objective while maintaining α-feasibility on V′; the candidates are scored on V, which no search has seen.Source: §3.2 · p. 6

3.3 GPU-ACCELERATED FEASIBILITY EVALUATION

  • Feasibility evaluation computes N×|V| independent candidate–scenario indicators in one batched GPU operation; the paper reports scoring 1,000 candidates over 10^6 scenarios in seconds.The passage notes that two-stage recourse generally precludes such batching unless the recourse has specific structure.Source: §3.3 · pp. 6–7

3.4 FEASIBILITY GUARANTEES

  • Because candidates are generated independently of V, a union bound limits the feasibility shortfall across N candidates; raising the selection threshold by ϵδ gives ACCESS(δ) a 1−δ guarantee.The guarantee uses independent samples and does not require a parametric assumption on P; with N=1000 and δ=0.05, the passage gives ϵδ=0.0022.Source: §3.4 · p. 7

4 COMPUTATIONAL RESULTS

The experiments compare ACCESS and ACCESS(δ) with SAA and safe approximations across Gaussian and non-Gaussian benchmarks. ACCESS is near the best feasible objective, while ACCESS(δ) is consistently feasible and conservative baselines trade objective quality for feasibility.

Experimental setup

  • The benchmarks cover KP, MWM, and SRCSP; the non-Gaussian figure reports KP with n=100 and α=0.99.Gaussian results use 20 instances per setting, and the main SAA and CVaR baselines use |S|=1000 scenarios.Source: §4 · p. 8, Figure 3 · p. 9

Evaluation

  • Feasibility is assessed on T=10^6 scenarios, separately from ACCESS’s selection set; FO-gap is reported only for methods feasible on T.The optimality gap in Figure 3 uses the same best α-feasible objective reference, but plots feasible and infeasible solutions alike.Source: §4 · p. 8, Figure 3 · p. 9

Results

  • 26 of 27 Gaussian settings: ACCESS attains the best or tied-best FO-gap, within 0.04% of the best known objective throughout.ACCESS(δ) is α-feasible on every instance, with a worst-case FO-gap of 0.64%.Source: §4 · p. 8, Table 1 · p. 9
  • Across non-Gaussian KP instances, ACCESS is α-feasible on nearly all instances with mean gap at most 0.32%, while CVaR is feasible on all 80 at lower quality.SAA falls below α on 65% of instances, even with |S|=10^4.Source: §4 · p. 8, Figure 3 · p. 9
  • Gaussian–Bonferroni is feasible on every instance and CVaR on all but three settings, but their objective losses are 1.6–7.5% and 0.9–10.4%, respectively.SAA’s reported gaps exclude infeasible cases; it is feasible on 0% of the two largest KP settings at α=0.99.Source: §4 · p. 8

Limitations

  • ACCESS’s cost assumes cheap deterministic subproblems and benefits substantially from parallel hardware; its guarantee covers feasibility, not objective value.Empirically, returned solutions lie within a fraction of a percent of the best objective found by any method.Source: §4 · p. 9

5 CONCLUSION

ACCESS reduces the search to a two-parameter space and uses Bayesian optimization to concentrate candidates near the feasibility boundary. ACCESS(δ) provides certified feasibility guarantees, and experiments report high-quality feasible solutions across the tested benchmarks.

5 CONCLUSION

  • ACCESS reduces the search from a high-dimensional solution space to a two-dimensional (γ, β) parameter space that captures the feasibility–optimality trade-off.Bayesian optimization concentrates candidates near the feasibility boundary; ACCESS(δ) provides certified guarantees with probability 1−δ.Source: §5 · p. 9

Appendix

  • The appendices cover benchmark details, certified guarantees, algorithmic details, non-standard uncertainty, ablations, baseline analysis, per-instance results, and runtimes.The paper identifies alternative probabilistic constraints, richer formulations, and search strategies beyond Bayesian optimization as future directions.Source: §5 · p. 9, Appendix · p. 13

A BENCHMARKS AND DETAILS

The paper evaluates three chance-constrained benchmark families, compares scenario-based and safe-approximation baselines, and develops a finite-candidate feasibility certificate for ACCESS(δ).

A BENCHMARKS AND DETAILS

  • Three benchmark families use multiplicative uncertainty: knapsack, maximum-weight bipartite matching, and stochastic resource-constrained shortest path.The Gaussian evaluation spans three sizes and confidence levels, with 20 held-out instances per setting; additional knapsack settings vary uncertainty structure.Source: A BENCHMARKS AND DETAILS · p. 14

A.1–A.3 BENCHMARKS

  • Knapsack selects items under random resource capacities, matching selects edges under random resource budgets, and shortest path selects arcs under random resource constraints.The benchmark passages specify instance sizes and generation details for each family.Source: §A.1 · p. 14, §A.2 · p. 14

B BASELINES

  • SAA and CVaR embed sampled scenarios in deterministic surrogates, while Gaussian–Bonferroni uses the uncertainty model without scenarios.Baselines are evaluated on a test set independent of their sampling set.Source: B BASELINES · p. 16

B.1 SAA FORMULATION

  • SAA linearizes the empirical chance constraint with one indicator per sampled scenario, allowing at most floor((1−α)|S|) sampled violations.The formulation uses big-M constants chosen to dominate sampled violations.Source: §B.1 · p. 16

B.2 SAFE APPROXIMATIONS

  • Safe approximations replace the chance constraint with a deterministic convex constraint that implies feasibility; row-wise bounds can be combined through risk splitting.The Bonferroni allocation ignores dependence between rows, which are strongly positively dependent in these benchmarks.Source: §B.2 · p. 16

C CERTIFIED FEASIBILITY GUARANTEES

  • ACCESS(δ) selects among candidates using a lower bound on true feasibility, accounting for selection bias from evaluating candidates on a shared set V.The candidate pool is generated independently of V, and the guarantee requires i.i.d. draws for V but no distributional assumptions.Source: C CERTIFIED FEASIBILITY GUARANTEES · p. 18, §C.1 · p. 18, §C.3 · p. 19

C.2 PROOF OF PROPOSITION 1

  • Hoeffding’s inequality and a union bound make the feasibility bound hold simultaneously for all N candidates with probability at least 1−δ.Because the event covers every candidate, it also covers whichever candidate the selection rule returns.Source: §C.2 · p. 18

C.3 RELATION TO SAA THEORY

  • ACCESS’s finite-candidate correction runs over N generated candidates rather than every decision in the SAA feasible region, whose multiplicity can be exponential.The candidate pool must be generated without using V.Source: §C.3 · p. 19

C.4 PRACTICAL IMPLICATIONS

The practical certificate uses a small feasibility margin, while the algorithmic details describe ACCESS’s solve budget, per-row uncertainty scaling, and search behavior as BO iterations and candidate counts grow.

D.1 HYPERPARAMETER SETTINGS

  • Each instance uses 15,040 single-threaded MILP solves with a 3 s limit, retaining one candidate per scenario for N=1000 candidates.Scenarios are processed in parallel.Source: §D.1 · p. 20, Table 3 · p. 20

D.2 ESTIMATING THE PER-ROW SCALE

  • For left-hand-side uncertainty, each row’s scale is average relative coefficient volatility in nominal units; right-hand-side uncertainty instead uses normalized RHS deviations.When both sides are uncertain, the deviations need to be combined into one per-row scale, for example by summing them.Source: §D.2 · pp. 20–21

D.3 BO CONVERGENCE

  • BO generally improves the running best with more iterations, except where initialization already finds high-quality solutions, as in low-α SRCSP.The running best is the best objective among points solved so far that pass the quick feasibility check; Figure 4 plots improvement over the initial quasi-random samples, with standard-error shading.Source: §D.3 · p. 21, Figure 4 · p. 21

D.4 SCALING WITH CANDIDATE BUDGET

  • Candidate quality improves rapidly before diminishing returns: SRCSP reaches its full-pool objective by N=50, while KP and MWM approach convergence on average by N=100.Some KP and MWM instances still benefit from more candidates; Figure 5 reports FO-gap relative to the best feasible objective at N=1000.Source: §D.4 · p. 21, Figure 5 · p. 22

D.5 PARAMETER SPACE ANALYSIS

Certified parameter choices show distinct patterns across benchmarks, and the paper also tests ACCESS under heterogeneous and non-Gaussian uncertainty rather than relying on homogeneous Gaussian assumptions.

D.5 PARAMETER SPACE ANALYSIS

  • Certified parameter choices differ by benchmark: KP uses γ⋆ in [0.3, 0.8] with β⋆ near zero, while MWM’s β⋆ rises at α=.99 and SRCSP spreads more broadly.Figure 6 plots each test instance, with colors for α ∈ {0.90, 0.95, 0.99}; the authors suggest SRCSP’s spread may reflect easier instances with more viable good solutions.Source: §D.5 · p. 22, Figure 6 · p. 23

E NON-STANDARD UNCERTAINTY

  • ACCESS is also evaluated with heterogeneous constraint scales and four non-Gaussian distributions, using samples from the problem distribution for candidate scoring rather than a distributional assumption.The evaluation changes uncertainty while keeping the instances, seeds, and multiplicative model from the Gaussian benchmark.Source: E NON-STANDARD UNCERTAINTY · p. 24

E.1 HETEROGENEOUS UNCERTAINTY ABLATION

The ablations examine per-row scaling under heterogeneous uncertainty and ACCESS’s behavior across non-Gaussian distributions, where the certified rule remains feasible across the tested instances.

E.1 HETEROGENEOUS UNCERTAINTY ABLATION

  • 10.23% vs GB’s 0.68%: the scalar-σ variant’s worst gap is larger as row-scale spread grows and α tightens, while ACCESS consistently computes best-known feasible solutions.The four medium-size knapsack settings vary per-row σ while sharing instances and seeds; the scalar variant matches ACCESS in homogeneous settings where the normalizations coincide.Source: §E.1 · p. 24, Table 4 · p. 25

E.2 NON-GAUSSIAN UNCERTAINTY

  • ACCESS(δ) is α-feasible on all 480 instances under every tested distribution; the uncorrected rule has 0.00–0.32% gaps at 80–100% feasibility.SAA finds no feasible solutions on some large, high-α instances, while CVaR remains feasible at large sample sizes but has worse objectives; its empirical feasibility can fall below α when tight tail estimates use few scenarios.Source: §E.2 · pp. 25–26, Table 5 · p. 26

F ABLATION: NOMINAL-ONLY TIGHTENING (β=0)

The nominal-only β=0 ablation tests whether scenario-specific diversification adds value beyond scalar tightening, while the SAA and CVaR results show the trade-offs of scenario-based and conservative alternatives.

F ABLATION: NOMINAL-ONLY TIGHTENING (β=0)

  • The β=0 ablation fixes constraint data at its nominal value and searches a 100-point grid over γ, isolating the benefit of per-scenario (γ, β) search.The scenario mixture varies uncertainty across sampled scenarios; nominal-only tightening varies only the tightening level.Source: F ABLATION: NOMINAL-ONLY TIGHTENING… · p. 27
  • ACCESS has at most 0.04% FO-gap on Gaussian benchmarks and is ahead of or tied with β=0 throughout; its advantage grows under non-Gaussian distributions.On the risky subset, the gain reaches +16.6%; median β⋆ is 0.36, and no instance chooses β⋆=0.Source: F ABLATION: NOMINAL-ONLY TIGHTENING… · p. 27, Table 6 · p. 27, Table 7 · p. 27

G.1 SAA

  • Small SAA samples hold in-sample but fail on held-out data, while |S|=10000 reaches the time limit and returns a more conservative incumbent.The larger-sample incumbent is more often feasible but has a larger gap.Source: §G.1 · p. 28, Table 8 · p. 28

G.2 CVAR

  • At α=0.99, CVaR fails even with |S|=1000; its Bonferroni allocation is overly conservative and significantly degrades results relative to SAA.Small samples leave only one or two scenarios in each row’s tail, making the estimate unsafe.Source: §G.2 · p. 28, Table 9 · p. 28

H PER-INSTANCE DISTRIBUTIONAL RESULTS

Across the three benchmarks, ACCESS’s per-instance results cluster near the feasibility threshold at low optimality gap, and its feasible candidates are generated quickly and concentrate near that boundary.

H.1 FEASIBILITY RATE VS. OPTIMALITY GAP

  • Across KP, MWM, and SRCSP, ACCESS sits near 0% gap just above the α-feasibility threshold, SAA falls below it, and CVaR and GB clear it at substantially larger gaps.The gap is measured against the best α-feasible objective found by any method; infeasible solutions can therefore appear at negative gaps.Source: §H.1 · p. 29, Figure 7 · p. 29, Figure 8 · p. 30

H.2 GENERATION TIME VS. FO-GAP

  • ACCESS reaches near-zero FO-gap in about two minutes on KP and SRCSP and about ten minutes on the largest MWM instances; SAA reaches an hour, while GB and CVaR are faster but have larger gaps.Only α-feasible solutions are included in the runtime comparison.Source: §H.2 · pp. 29–30, Figure 10 · p. 32, Figure 11 · p. 33

H.3 FEASIBILITY DISTRIBUTIONS: ACCESS VS RANDOM SAMPLING

  • Across instance sizes and α values, ACCESS candidates concentrate near the feasibility boundary, while random sampling often yields completely feasible or infeasible solutions.The comparison evaluates each candidate on 10^6 scenarios and pools results across 20 test instances.Source: §H.3 · p. 30, Figure 13 · p. 35, Figure 14 · p. 36

I DETAILED RUNTIME RESULTS

Table 10 separates ACCESS generation and feasibility-checking times; checking accounts for a small share of total time.

I DETAILED RUNTIME RESULTS

  • Feasibility checking takes 2–13% of ACCESS’s total time, so enlarging the evaluation set for a tighter certificate costs little.Table 10 reports mean generation times across 20 test instances for each benchmark, size, and α, with ACCESS times split into generation and feasibility.Source: I DETAILED RUNTIME RESULTS · p. 38, Table 10 · p. 38
  • Table 10 reports mean generation-time statistics across 20 test instances, broken out by benchmark, size, and α.ACCESS entries are shown as generation time followed by feasibility-checking time.Source: I DETAILED RUNTIME RESULTS · p. 38, Table 10 · p. 38
  • The split distinguishes BO search time from final constraint verification, making the cost of checking visible separately.The table presents ACCESS times in generation/feasibility order.Source: I DETAILED RUNTIME RESULTS · p. 38, Table 10 · p. 38
Loading 2610.19027v1…