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

Justin Dumouchelle; Shunyu Yao; Beste Basciftci; Thiago Serra

math.OCOct 13, 2026

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

Authors: Justin Dumouchelle, Shunyu Yao, Beste Basciftci, Thiago Serra

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 $1-δ$ . 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 $\alpha{=}0.90$ , one point per instance. Gap is relative to the best $\alpha$ -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 $1{,}000$ candidates from random $(\gamma,\beta)$ pairs and of the $1{,}000$ ACCESS candidates, on a single knapsack instance.

Figure 2: The ACCESS pipeline. (1) For each of the

N

sampled scenarios, constrained BO searches over

(\gamma,\beta)

, in parallel on CPU. (2) The resulting candidates

\mathbf{x}^{(1)},\dots,\mathbf{x}^{(N)}

are scored against a set of validation scenarios

\mathcal{V}

in one batched GPU pass, and the best

\alpha

-feasible solution is returned.

Small

Medium

Large

Method

Time

\alpha{=}.90

\alpha{=}.95

\alpha{=}.99

Time

\alpha{=}.90

\alpha{=}.95

\alpha{=}.99

Time

\alpha{=}.90

\alpha{=}.95

\alpha{=}.99

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%

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

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(

\delta

)

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 /

\alpha

-feasibility rate, followed by runtime in seconds (averaged over

\alpha

values). FO-gap is relative to BKO (Best Known Objective): the best

\alpha

-feasible objective across all methods per instance. SAA and CVaR use

|\mathcal{S}|{=}1000

scenarios; ACCESS(

\delta

) applies Hoeffding correction with

\delta{=}0.05

. Sizes: KP:

n\in\{20,50,100\}

d\in\{3,5,10\}

; MWM:

10\times 10/15\times 15/20\times 20

d=5

; SRCSP:

|A|\in\{20,50,100\}

d\in\{3,5,10\}

. Each entry is averaged over 20 test instances.

Figure 3: Feasibility rate vs. optimality gap under non-Gaussian distributions, on KP with

n{=}100,\alpha{=}0.99

. Each point is one of 20 instances, and the dashed line marks

\alpha

. SAA and CVaR use

|\mathcal{S}|{=}10^{4}

. Gap is relative to the best

\alpha

-feasible objective, so infeasible solutions may have negative gaps.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Method	$\|\mathcal{V}\|$	Empirical $\hat{p}$	Hoeffding lower bound
SAA-favorable ( $S=1000$ , $N=1$ )	1,000	0.99	0.951
ACCESS ( $\|\mathcal{V}\|=10^{6}$ , $N=1000$ )	1,000,000	0.99	0.988

Appendix

Table 2: Hoeffding lower bounds on true feasibility for an observed empirical rate of

\hat{p}=0.99

, with

\delta=0.05

Parameter	Value	Description
Scenario Sampling
$N_{\text{scen}}$	1000	Scenarios drawn from the problem’s own distribution $\mathbb{P}$
Bayesian Optimization (per scenario)
$N_{\text{init}}$	5	Initial Sobol samples
$N_{\text{iter}}$	10	BO iterations after initialization
Acquisition	qLogEI	Log expected improvement, feasibility-constrained

Appendix

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

N

(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

N{=}1000

. Higher

\alpha

(red) generally requires more candidates to achieve low FO-gap. Shaded regions show standard error across 20 test instances.

Figure 6: Selected parameters

(\gamma^{\star},\beta^{\star})

per instance. Each point represents one test instance; colors denote

\alpha\in\{0.90,0.95,0.99\}

. Rows correspond to benchmarks and columns to instance sizes.

	Method	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
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 $\bar{\sigma}$ )	0.00% / 95%	0.04% / 100%	0.00% / 100%

Appendix

Table 4: Heterogeneous uncertainty on the knapsack benchmark (

n{=}50

d{=}5

). Each cell reports FO-gap /

\alpha

-feas rate over 20 seeds, with feasibility measured on

10^{6}

held-out scenarios. The four settings share instances and seeds and differ only in the per-row

\sigma_{d}

; hom_20 is Medium KP from the main results.

		$n{=}50$ , $d{=}5$			$n{=}100$ , $d{=}10$
	Method	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
Student- $t_{3}$	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%

Appendix

Table 5: Non-Gaussian uncertainty on the knapsack benchmark. Each cell reports FO-gap /

\alpha

-feas rate over 20 seeds, with feasibility measured on

10^{6}

held-out scenarios from the same distribution.

		Small			Medium			Large
	Method	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
KP	ACCESS	0.00	0.01	0.00	0.00	0.04	0.00	0.01	0.01	0.00
	$\beta{=}0$	0.09	0.18	0.11	0.19	0.28	0.26	0.34	0.33	0.37
	$\Delta$	+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
	$\beta{=}0$	0.19	0.17	0.43	0.35	0.21	0.73	0.26	0.39	0.66

Appendix

Table 6: Ablation: ACCESS vs. the nominal-only (

\beta{=}0

) variant, both under the uncertified rule. Rows report FO-gap (%) against BKO;

\Delta

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- $t_{3}$	120	+0.38%	104	14	2
Jump	120	+0.72%	117	3	0
Clustered	120	+0.81%	110	4	6

Appendix

Table 7: Mean paired objective gain of ACCESS over the nominal-only (

\beta{=}0

) variant, both under the uncertified rule. Win, tie and loss count the instances on which ACCESS is ahead, equal and behind.

		Small			Medium			Large
	$\|\mathcal{S}\|$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
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%

Appendix

Table 8: SAA results varying sample size

|\mathcal{S}|

. Each cell reports FO-gap /

\alpha

-feas rate. Time limit: 3600 s.

		Small			Medium			Large
	$\|\mathcal{S}\|$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
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%

Appendix

Table 9: CVaR results varying sample size

|\mathcal{S}|

. Each cell reports FO-gap /

\alpha

-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

\alpha

-feasible solutions only.

Figure 11: Generation time versus FO-gap for MWM, over the

\alpha

-feasible solutions only.

Figure 12: Generation time versus FO-gap for SRCSP, over the

\alpha

-feasible solutions only.

Figure 13: Feasibility distributions for Knapsack (KP). Rows are instance sizes and columns are

\alpha

Figure 14: Feasibility distributions for Maximum Weight Matching (MWM).

Figure 15: Feasibility distributions for Stochastic Resource-Constrained Shortest Path (SRCSP).

		Small			Medium			Large
	Method	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$	$\alpha{=}.90$	$\alpha{=}.95$	$\alpha{=}.99$
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

Appendix

Table 10: Generation time in seconds (mean across 20 instances). ACCESS times shown as generation/feasibility.

Chance-Constrained Optimization

Chance-constrained optimization chooses decisions that optimize performance while limiting the probability of violating uncertain constraints.

See all 29 papers

Oct 2, 2026

Learn Feasibility Once, Optimize All Objectives: Derivative-Free Diffusion Models for Chance-Constrained Programming

Chance-constrained programs (CCPs) optimize decisions under uncertainty by limiting the probability of constraint violation. Despite advances in traditional and learning-based approaches, optimizing non-convex or non-smooth objectives and adapting to different objectives under fixed chance constraints remain challenging. In this paper, we propose a Derivative-free Diffusion-based framework that Disentangles constraint modeling from objective optimization, termed \textbf{D

^3

Opt}. We learn the chance-feasible structure once, independently of any particular objective, by training a risk-conditioned diffusion model solely on constraint-filtered decisions and freezing it as a reusable prior for post-specified objectives. At inference time, we propose an annealed, particle-based Feynman--Kac correction along the frozen reverse diffusion process to optimize post-specified objectives using only function evaluations. This enables derivative-free optimization of non-convex and non-smooth objectives without objective-specific retraining. We prove that the correction preserves feasibility when this property holds for the frozen prior, and derive an optimization-error bound separating learned-prior coverage, finite-particle approximation, and finite-temperature effects. Experiments on linear Gaussian CCPs, objective-transfer tasks, and chance-constrained economic dispatch demonstrate effective optimization across smooth and non-smooth objectives, including non-convex cases, and objective generalization under fixed chance constraints without retraining.

Ziwen Liu, Yan Liu, Congying Han +3

School of Mathematical Sciences, Beijing University of Posts and Telecommunications · School of Statistics and Data Science, Nankai University · School of Mathematical Sciences, University of the Chinese Academy of Sciences +1

Chance-Constrained Optimization Diffusion Models Derivative-Free Optimization Nonconvex Optimization

Ask PDF

Feb 12, 2024

Conformal Predictive Programming for Chance Constrained Optimization

We propose conformal predictive programming (CPP), a framework to solve chance constrained optimization problems, i.e., optimization problems with constraints that are functions of random variables. CPP utilizes samples from these random variables along with the quantile lemma - central to conformal prediction - to transform the chance constrained optimization problem into a deterministic problem with a quantile reformulation. CPP's main strength is an independent calibration step that provides a posteriori guarantees for the solution of this problem that are of conditional and marginal nature otherwise. These guarantees even apply in settings when assumptions required for obtaining standard a priori guarantees (e.g., in scenario optimization or sample average approximation) are unavailable, difficult to compute, or conservative. Another strength of CPP is that it can easily support different variants of conformal prediction which have been (or will be) proposed within the conformal prediction community. To illustrate this, we present robust CPP to deal with distribution shifts in the random variables and Mondrian CPP to deal with class conditional chance constraints. In a series of case studies, we show the validity of the aforementioned approaches, and illustrate the advantage of CPP as compared to scenario approach.

Yiqi Zhao, Xinyi Yu, Matteo Sesia +2

Thomas Lord Department of Computer Science, University of Southern California · Department of Data Sciences and Operations, University of Southern California · Automatic Control Laboratory, ETH Zürich

Stochastic Optimization Chance-Constrained Optimization Conformal Prediction Constrained Optimization

Ask PDF

Mar 19, 2026

Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints

In this paper, we present an equivalent convex optimization formulation for discrete-time stochastic linear systems subject to linear chance constraints, alongside a tight convex relaxation for quadratic chance constraints. By lifting the state vector to encode moment information explicitly, the formulation captures linear chance constraints on states and controls across multiple time steps exactly, without conservatism, yielding strict improvements in both feasibility and optimality. For quadratic chance constraints, we derive convex approximations that are provably less conservative than existing methods. We validate the framework on minimum-snap trajectory generation for a quadrotor, demonstrating that the proposed approach remains feasible at noise levels an order of magnitude beyond the operating range of prior formulations.

Tanmay Dokania, Yashwanth Kumar Nakka

Authors are with the Daniel Guggenheim School of Aerospace Engineering at the Georgia Institute of Technology, Atlanta, GA, 30332 USA.

Stochastic Optimal Control Chance-Constrained Optimization Stochastic Linear Dynamical Systems

Ask PDF

Abstract

Chance-Constrained Optimization

Explore similar work

Learn Feasibility Once, Optimize All Objectives: Derivative-Free Diffusion Models for Chance-Constrained Programming

Conformal Predictive Programming for Chance Constrained Optimization

Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints