acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
optimization
Keywords:
stochastic programming, combinatorial optimization, integer programming, bayesian optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7cD7OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ACCESS, a sampling framework for chance-constrained stochastic programs. Instead of solving a large scenario-based optimization problem, ACCESS generates candidate solutions by solving single-scenario mixed-integer programs. Bayesian optimization searches this two-dimensional parameter space, while GPU-accelerated simulation evaluates candidate feasibility.

Critical strengths
  1. Decoupling candidate generation from feasibility evaluation is interesting for combinatorial chance-constrained problems. The ability to solve small deterministic subproblems in parallel and evaluate large numbers of scenarios efficiently on GPUs is a useful computational contribution.

  2. The paper studies three problems under several uncertainty distributions. The reported results suggest that ACCESS can efficiently produce high-quality feasible solutions.

Critical weaknesses
  1. The numerical study compares ACCESS primarily against basic SAA, Gaussian–Bonferroni, and a row-wise CVaR approximation using uniform Bonferroni risk allocation. The CVaR baseline is particularly conservative: when α=0.99\alpha=0.99, d=10d=10, and ∣S∣=1000|S|=1000, the row-wise risk allocation reduces the sample CVaR constraints to enforcing every sampled constraint.

  2. The main mathematical result, Proposition 1, follows directly from Hoeffding's inequality and a union bound over a finite candidate set.

  3. The paper provides no theoretical guarantee on objective quality, approximation bound, or convergence toward the optimal chance-constrained solution.

Questions for authors
  1. Why are stronger approximation algorithms in recent literature not included?

  2. Can the authors show any approximation guarantee or convergence result as the number of candidate solutions increases?

  3. Proposition 1 shows the feasibility of candidates passing the validation threshold, but does not guarantee that such a candidate exists. How does ACCESS(δ\delta) handle an empty candidate set?

  4. How does the performance of ACCESS compare with random or quasi-random sampling of (γ,β)(\gamma,\beta) using the same number of subproblem solves?

  5. Can the authors report objective bounds or comparisons with best-known optimal values on smaller instances?

3 comments
AuthorsOpenReview ↗

Reply to Reviewer 7cD7

We thank the reviewer for the constructive review. The general response addresses the joint CVaR baseline and strengthened SAA formulations (G1), the comparison against random search (G2), feasibility of the candidate pool (G3), and scalability (G4). The comparison against known optimal values with risk-level tuning of SAA is new and reported under Q5. In addition, we reply to each point below.

Weaknesses

W1 — Baselines. The reviewer is correct that the row-wise CVaR is a weak baseline, and we have added the joint CVaR formulation on all instances (G1). The joint formulation roughly halves the FO-gap of the row-wise one and still trails ACCESS by a clear margin. At S=103S = 10^3 it is also less feasible than the row-wise form, since it is less conservative. On strengthened SAA formulations, we refer to G1: they reach the same SAA optimum faster but do not change its feasibility on held-out scenarios. The remedy for that is more scenarios or a tightened risk level, which we study in Q5.

W2 — Proposition 1 and the non-empty candidate set. We agree that Proposition 1 is a direct application of Hoeffding's inequality with a union bound. Its value lies in what it is applied to: SAA's guarantees require a union bound over the feasible region of the sample problem, whereas ACCESS certifies NN explicit candidates that were generated without the validation scenarios, so the certificate can use 10610^6 scenarios at negligible cost. That the candidate set is non-empty is supported by the initialization rather than by the bound, as discussed in G3, and in non-pathological cases, we expect this procedure to be sufficient to ensure feasible candidates.

W3 — No guarantee on objective quality, and gaps measured against BKO. We do not claim an approximation ratio, and we will make this explicit and distinguish relative objective differences measured against the Best Known Objective (BKO) from certified optimality gaps. The guarantees available for existing approaches also require careful qualification. Conservative approximations ensure feasibility under their distributional and modeling assumptions; implementations based on estimated distributions require additional control of estimation error. Such safety does not generally imply an objective-quality guarantee: the CVaR approximation can be arbitrarily bad in the worst case, even for a problem with one continuous decision variable and a linear uncertain constraint [7]. Positive objective guarantees exist under additional assumptions: for example, CVaR is asymptotically optimal for certain structured linear problems with light-tailed distributions as the allowed violation probability tends to zero [8]. This is a different asymptotic regime from increasing the sample size at a fixed risk level.

SAA offers both asymptotic and finite-sample guarantees. Under suitable assumptions, its optimal objective values converge to the true optimal value [2]. Furthermore, appropriate risk calibration and independent replications can yield statistical bounds on the true optimal value. Accordingly, we interpret our SAA comparisons as empirical evidence of objective quality. In the absence of a bound, SAA solutions provide a practically useful reference. SAA optimizes against the sampled constraints, so when its solution is infeasible on held-out scenarios, its objective can be an optimistic estimate of what a feasible solution can achieve. On instances where SAA’s solution is infeasible, ACCESS achieves an objective within 0.4% of SAA’s on average at (S=104S=10^4), while remaining feasible. That said, we acknowledge that we are not comparing against true optimal values because of the scale of the instances. We will therefore present these results as objective comparisons, not certified optimality gaps, and distinguish infeasible SAA references from the BKO among feasible solutions. To complement these comparisons, Q5 adds a study on instances small enough to enumerate: ACCESS returns the exact optimum on 95–100% of the instances where it returns a feasible solution.

Questions

Q1 — Stronger approximation algorithms, strengthened SAA, and joint CVaR. The joint CVaR is added on all instances and strengthened SAA formulations are discussed in G1. Risk-level tuning of SAA is reported in Q5.

Q2 — Approximation guarantee, sufficient condition, or convergence result. As we focus on a general CCSP setting, guarantees without strong setting-specific assumptions are often rare for safe/conservative approximations as well. We therefore focus on the computational elements to demonstrate efficacy, combined with our feasibility guarantees, as a practical alternative. We will state this in the paper. We assess solution quality empirically and provide additional results in (Q5), including against the exact optimum on small instances.

Q3 — Empty candidate set and the probability of generating a feasible solution. The nominal initialization seeds the pool with conservative candidates, making certification failure unlikely in practice (G3). If no candidate passes the certified threshold, we report that no certified solution was found and label any fallback as uncertified. This did not occur in any of the 1,200 instances, and the median pool has 841 of 1,001 candidates above the certified threshold.

Q4 — Random or quasi-random sampling with the same number of subproblem solves. We now report this comparison on all 1,200 instances (G2). With the same budget, ACCESS-random is within 0.1% of ACCESS on average with similar feasibility. The trade-off is convergence: BO improves a scenario's best feasible objective about twice as much per added point and reaches the quality of the full random run with about a quarter of the subproblem solves, so we keep it as the default.

Q5 — Comparison with optimal values on smaller instances, and risk-level tuning of SAA. We added a set of 10-item, 2-constraint knapsack instances (20 seeds for each α\alpha) on which all 1,024 solutions are enumerated and evaluated on the 10610^6 test scenarios, so the exact optimum is known (under the large scale empirical distribution). All methods were run on these instances. For risk-level tuning, we solve SAA at S∈{103,104}S \in \{10^3, 10^4\} with a tightened risk level inside the model: the SAA problem requires feasibility on a fraction α′=1−c(1−α)\alpha' = 1 - c(1-\alpha) of the scenarios, for c∈{1,0.9,…,0.5}c \in \{1, 0.9, \ldots, 0.5\}, while the returned solution is still evaluated against the target α\alpha. Here c=1c = 1 is standard SAA, and smaller cc allows fewer violated scenarios and is therefore more conservative (e.g., for α=0.90\alpha = 0.90, c=0.5c = 0.5 gives α′=0.95\alpha' = 0.95). Every SAA model was solved to optimality. Each cell reports the mean gap to the exact optimum (%) over the α\alpha-feasible instances / % of instances α\alpha-feasible / % of feasible instances returning the exact optimum.

methodα=0.90\alpha = 0.90α=0.95\alpha = 0.95α=0.99\alpha = 0.99
ACCESS0.11 / 100 / 950.02 / 100 / 950.00 / 90 / 100
ACCESS(δ\delta)0.15 / 100 / 900.15 / 100 / 900.55 / 100 / 65
SAA (S=103S = 10^3)0.89 / 85 / 760.16 / 80 / 880.35 / 60 / 83
SAA (S=104S = 10^4)0.05 / 95 / 950.21 / 100 / 900.00 / 80 / 100
CVaR joint (S=104S = 10^4)4.65 / 100 / 154.14 / 100 / 52.26 / 100 / 15
GB4.06 / 100 / 152.30 / 100 / 301.71 / 100 / 30

The next table reports the largest cc (the least conservative setting) at which SAA is α\alpha-feasible on every instance, and the gap to the exact optimum it then incurs.

SAAα=0.90\alpha = 0.90α=0.95\alpha = 0.95α=0.99\alpha = 0.99
S=103S = 10^3c=0.7c = 0.7, 2.25%c=0.9c = 0.9, 0.18%none (95% feasible for c≤0.6c \leq 0.6)
S=104S = 10^4c=0.9c = 0.9, 1.15%c=1c = 1, 0.21%c=0.8c = 0.8, 0.37%

Since these instances can be enumerated, we can also compute the SAA optimum for scenario counts that are out of reach for the MILP, by selecting the best solution that satisfies the sampled constraint (c=1c = 1). The cells follow the format of the first table.

SAA by enumerationα=0.90\alpha = 0.90α=0.95\alpha = 0.95α=0.99\alpha = 0.99
S=105S = 10^50.00 / 95 / 1000.02 / 95 / 950.00 / 90 / 100
S=106S = 10^60.00 / 100 / 1000.02 / 100 / 950.00 / 95 / 100
S=107S = 10^70.00 / 100 / 1000.02 / 100 / 950.00 / 95 / 100

The feasibility of SAA increases steadily with the number of scenarios, and from S=106S = 10^6 it essentially recovers the exact optimum, which indicates that its failures at smaller SS are due to sampling error. The one remaining infeasible instance at α=0.99\alpha = 0.99 has a solution whose feasibility is 0.99001 on the 10710^7 SAA scenarios and 0.98997 on the 10610^6 test scenarios, i.e., it lies on the boundary to within the resolution of the test set. Such scenario counts are only attainable here through enumeration, whereas ACCESS uses 10610^6 scenarios in its evaluation step at a cost of seconds.

ACCESS returns the exact optimum on 95–100% of the instances where it is feasible. Its two infeasible cases at α=0.99\alpha = 0.99 lie on the boundary in the same sense (0.98999 and 0.98997 on the test set). ACCESS(δ\delta) is within 0.15–0.55% with every instance feasible. Risk-level tuning makes SAA feasible at an objective cost of 0.2–2.3%, and at α=0.99\alpha = 0.99 with S=103S = 10^3 no value of cc reaches full feasibility. We note that the value of cc reported for SAA is selected with knowledge of the test outcome, whereas ACCESS(δ\delta) fixes its margin in advance through δ\delta. These small instances are favorable to SAA, since it can be solved to optimality with 10410^4 scenarios in minutes. On the instances of the main paper, SAA with S=104S = 10^4 reaches the one-hour limit and is infeasible on a quarter of the instances.

Reviewer_GCn2OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ACCESS, a framework for chance-constrained stochastic optimization that decouples candidate generation from feasibility evaluation. It uses Bayesian optimization over a two-dimensional parameter space to generate high-quality solutions and GPU-accelerated simulation to assess feasibility. A certified variant, ACCESS(δ), provides probabilistic feasibility guarantees. Experiments demonstrate strong solution quality and computational efficiency across multiple combinatorial optimization benchmarks.

Critical strengths
  1. The decoupling of optimization and feasibility evaluation is intuitive and computationally effective.
  2. The distribution-free feasibility guarantee provides a solid theoretical foundation.
  3. Extensive experiments demonstrate strong objective quality and feasibility across different problem settings.
Critical weaknesses
  1. How does ACCESS compare with random search or other lightweight optimization strategies under the same computational budget?
  2. How well does the framework scale to larger real-world instances or settings where deterministic subproblems are expensive?
  3. How does ACCESS compare with random search or other lightweight optimization strategies under the same computational budget?
Questions for authors
  1. How does ACCESS compare with random search or other lightweight optimization strategies under the same computational budget?
  2. How well does the framework scale to larger real-world instances or settings where deterministic subproblems are expensive?
  3. What happens if no candidate satisfies the certified feasibility threshold? Rating
1 comment
AuthorsOpenReview ↗

Reply to Reviewer GCn2

We thank the reviewer for the questions. The general response addresses the comparison against random search (G2), feasibility of the candidate pool (G3), and scalability (G4). In addition, we reply to each point below.

Weaknesses

W1, W3 — Comparison with random search under the same computational budget. We now report this comparison on all 1,200 instances (G2). With the same budget, ACCESS-random, which replaces the BO iterations by an equal number of random points, is within 0.1% of ACCESS on average with similar feasibility. Random search therefore suffices to reach a comparable result, which we take as evidence that the parameterization, rather than the optimizer, is what makes the method work. The trade-off is convergence: BO improves a scenario's best feasible objective about twice as much per added point and reaches the quality of the full random run with about a quarter of the subproblem solves, so we keep it as the default.

W2 — Scalability to larger instances or expensive deterministic subproblems. We discuss instance scale in G4. ACCESS generates candidates through independent deterministic MILPs, which can be solved in parallel without embedding thousands of scenarios in each optimization model. With the search budget and number of workers fixed, doubling the average deterministic solve time roughly doubles ACCESS’s candidate-generation time. Scenario-coupled formulations retain the underlying combinatorial difficulty while adding interactions among scenario constraints, so we expect them to scale less favorably when many scenarios are needed in addition to problem complexity. ACCESS is also anytime, allowing the number of subproblems to be set by the available budget.

Questions

Q1 — Comparison with random search under the same computational budget. Please see W1 above and G2.

Q2 — Scalability to larger instances or expensive deterministic subproblems. Please see W2 above and G4.

Q3 — What happens if no candidate satisfies the certified feasibility threshold? The nominal initialization seeds the pool with conservative candidates, making certification failure unlikely in practice (G3). If no candidate passes the certified threshold, we report that no certified solution was found and label any fallback as uncertified. This did not occur in any of the 1,200 instances, and the median pool has 841 of 1,001 candidates above the certified threshold.

Reviewer_SwaxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed ACCESS, a framework for chance-constrained optimization. Specifically, it first generates candidate solutions by solving parameterized single-scenario MILPs with Bayesian optimization. It then selects feasible solutions through GPU-based scenario evaluation.

Critical strengths
  1. Decoupling optimization from feasibility evaluation is a reasonable approach, which could avoid solving large-scale problems.

  2. The two-parameter formulation provides clear interpretation. The ACCESS(δ) variant also provides theoretical feasibility guarantees.

  3. The numerical results showed significant performance gain in both solution quality and feasibility across different problem classes and uncertainty distributions.

Critical weaknesses
  1. The novelty seems to be relatively limited. The idea of decoupling candidate search from GPU-based scenario evaluation has been explored in previous works.[1] The Bayesian optimization and feasibility certification also appeared in existing frameworks.

  2. It is not clear whether the need of Bayesian optimization is necessary. Is it possible random search or grid search are also sufficient.

  3. The performance comparision in the numerical results does not seem to be very fair. SAA uses vanilla big-M formulation, while CVaR and GB rely on complex approximations.

  4. From the reported data, the scalability is not clear. The tested instances are relatively small, while ACCESS needs to solve more than 15,040 MILPs. It can be computationally impossible for larger MILPs.

[1] Zhao, Jingyi, et al. "From Sequential to Parallel: Reformulating Dynamic Programming as GPU Kernels for Large-Scale Stochastic Combinatorial Optimization." arXiv preprint arXiv:2602.05179 (2026).

[2] Berkenkamp, Felix, Andreas Krause, and Angela P. Schoellig. "Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics." Machine learning 112.10 (2023): 3713-3747.

Questions for authors
  1. Is it possible that there will not be any feasible solutions? For example, what if the MILP is too hard to be solved, or the feasibility is extremely hard to be satisfied?

  2. Is it possible to discuss how does the hardware requirement change as the scale of problems changes?

2 comments
AuthorsOpenReview ↗

Reply to Reviewer Swax

We thank the reviewer for the positive assessment and the questions. The general response addresses the stronger baselines (G1), the comparison against random search (G2), feasibility of the candidate pool (G3), and scalability (G4). In addition, we reply to the weaknesses and questions below.

Weaknesses

W1 — Novelty relative to GPU-parallel scenario evaluation [1] and safe Bayesian optimization [2]. We agree that [1] (numbered as in the review, as is [2]) also decouples candidate search from GPU-batched scenario evaluation, and that [2] also pairs Bayesian optimization with a feasibility certificate. The difference lies in what is decoupled and what is certified. In [1], the GPU solves the second-stage recourse of a two-stage SAA by dynamic programming and the first stage is searched with standard VRP heuristics, whereas in ACCESS the GPU evaluates chance-constraint feasibility and the candidates come from the parameterized subproblem family of Section 3.1. In [2], the certificate guarantees that the parameters BO evaluates are safe, whereas in ACCESS it guarantees the feasibility of the returned solution, from held-out scenarios and without assumptions on the distribution. The settings are also distinct: neither applies to a chance-constrained combinatorial program as such, and it is the parameterization and the pool-based certificate of this paper that make decoupled evaluation and BO usable in that setting. We will include this discussion in the revision.

W2 — Necessity of Bayesian optimization. We discuss this in G2. Random search (and, by extension, a grid over the two parameters) suffices to reach a comparable result, and we now report it on all 1,200 instances: with the same budget, ACCESS-random is within 0.1% of ACCESS on average with similar feasibility. The trade-off is convergence: BO improves a scenario's best feasible objective about twice as much per added point and reaches the quality of the full random run with about a quarter of the subproblem solves, so we keep it as the default.

W3 — Fairness with baselines. The baselines are the standard forms of each approach (the big-M scenario formulation for SAA, the standard linear form for CVaR, and the closed-form Gaussian approximation for GB), and all are evaluated on the same 10610^6 held-out scenarios. Strengthened SAA formulations reach the same optimal value faster but do not change its feasibility on held-out scenarios (G1). Where the sample-based side could be strengthened we have done so: the joint CVaR (G1) is added at S∈{103,104}S \in \{10^3, 10^4\}, and SAA is additionally run with tuned risk levels on a small-instance study (response to Reviewer 7cD7, Q5).

W4 — Scalability. We discuss instance scale in G4. In brief, every method for chance-constrained programs has scale limitations, and ACCESS places the fewest restrictions on the complexity of the problem: its subproblems are independent deterministic MILPs, without the big-M constraints, second-order cones, or scenario copies that limit the baselines. It is also anytime, so the pool and its certificate are valid at any point of the search and the number of subproblems can be set by the available budget. For example, Appendix E.6 reports the FO-gap as a function of the number of scenarios, and on KP and SRCSP with 100 scenarios instead of 1,000, a tenth of the subproblems, the returned objective is already within a fraction of a percent of the full run. In runtime, the 15,040 subproblems take 1.5 to 10 minutes per instance in total, less than a single SAA solve with a modest scenario budget: SAA with S=103S = 10^3 takes roughly 10 minutes on the smallest KP instances and reaches the one-hour limit on the larger KP and MWM instances. ACCESS therefore scales at least as well as existing methods for CCSP on these benchmarks.

Questions

Q1 — No feasible solution, or the MILP is too hard, or feasibility is extremely hard to satisfy? Failure to find a feasible candidate is possible in extreme cases, but is unlikely with our conservative initialization. G3 explains the initialization and the remaining possibility of certification failure. Expensive deterministic MILPs are a limitation shared with the baselines, which retain the underlying combinatorial structure while adding scenario-dependent constraints or conservative reformulations. ACCESS avoids coupling scenarios within optimization and solves its subproblems independently in parallel, giving it favorable prospects for scaling. We discuss this advantage and the expensive-subproblem regime in G4.

Q2 — How does the hardware requirement change with problem scale? Candidate generation needs CPUs only: the single-thread subproblem solves are independent, so the cost is linear in the time of one deterministic solve and parallelizes across cores. Evaluation processes scenarios in chunks, so memory is that of one chunk, and time is linear in the number of scenarios and candidates. This requires 3–15 s per instance on one GPU at 10610^6 scenarios, or a few minutes on a CPU if no GPU is available. As the problem scales, both steps benefit roughly linearly from more cores or more GPUs.

Comments on the paper

5 comments
AuthorsOpenReview ↗

General Rebuttal

We thank the reviewers. The reviews converge on four shared points: (1) the strength of the baselines, (2) whether Bayesian optimization is needed, (3) whether the candidate pool always contains a feasible solution, and (4) the scale of the instances. We address each in this thread as part of a general rebuttal with new experiments where applicable. Within the individual responses, we refer to these sections (G1–G4) and answer the remaining points.

ACCESS should be viewed as an integrated candidate-generation and certification framework rather than as GPU evaluation or BO in isolation: its two-parameter deterministic subproblems systematically generate near-boundary combinatorial solutions, which can be explored efficiently with BO or, as our new experiments show, with a competitive lower-overhead quasi-random search, and then selected using independent large-sample evaluation and certification. The ablations further isolate the value of this structure: removing scenario diversification (β=0\beta=0) reduces solution quality, particularly under the non-Gaussian distributions where nominal tightening alone cannot capture heterogeneous or correlated uncertainty, while replacing BO with quasi-random search largely preserves performance. Together, these results show that the main gains arise from the structured candidate family and its decoupling from certification, with BO serving as a sample-efficient rather than indispensable search mechanism.

G1. Baselines

Joint CVaR. Reviewer 7cD7 is right that the row-wise CVaR is a weaker baseline than the joint CVaR approximation. Therefore, we added the joint approximation, the CVaR at level 1−α1-\alpha of the row-wise maximum violation with rows scaled by their nominal capacity [1], on every instance at S∈103,104S \in { 10^3, 10^4 } scenarios. Below, we provide results that extend Table 1 of the main paper with SAA, CVaR, and the base variant of ACCESS. Each cell reports the mean FO-gap (%, lower is better) over the α\alpha-feasible instances / % of the 20 instances α\alpha-feasible on the 10610^6 test scenarios. Bold marks the best gap in the column.

KP

methodSmall α=.90\alpha=.90Small α=.95\alpha=.95Small α=.99\alpha=.99Medium α=.90\alpha=.90Medium α=.95\alpha=.95Medium α=.99\alpha=.99Large α=.90\alpha=.90Large α=.95\alpha=.95Large α=.99\alpha=.99
SAA (S=103S=10^3)0.08 / 750.11 / 500.00 / 450.21 / 400.19 / 25— / 00.11 / 250.29 / 5— / 0
SAA (S=104S=10^4)0.10 / 850.10 / 700.04 / 800.12 / 900.04 / 750.03 / 300.19 / 950.14 / 700.06 / 30
CVaR row-wise (S=103S=10^3)5.82 / 1004.88 / 1003.33 / 1004.16 / 1003.40 / 1001.37 / 853.25 / 1002.45 / 1000.89 / 35
CVaR joint (S=103S=10^3)3.05 / 1002.68 / 1001.71 / 1001.89 / 1001.56 / 1000.94 / 501.27 / 1001.05 / 1000.60 / 25
CVaR row-wise (S=104S=10^4)6.00 / 1005.26 / 1004.39 / 1004.51 / 1004.02 / 1003.12 / 1003.81 / 1003.34 / 1002.38 / 100
CVaR joint (S=104S=10^4)3.27 / 1002.60 / 1002.38 / 1001.96 / 1001.71 / 1001.34 / 1001.35 / 1001.19 / 1000.92 / 100
ACCESS0.00 / 1000.01 / 1000.00 / 1000.00 / 950.04 / 1000.00 / 1000.01 / 1000.01 / 900.00 / 95

MWM

methodSmall α=.90\alpha=.90Small α=.95\alpha=.95Small α=.99\alpha=.99Medium α=.90\alpha=.90Medium α=.95\alpha=.95Medium α=.99\alpha=.99Large α=.90\alpha=.90Large α=.95\alpha=.95Large α=.99\alpha=.99
SAA (S=103S=10^3)0.09 / 750.17 / 750.13 / 550.80 / 850.62 / 550.11 / 551.38 / 650.84 / 800.04 / 40
SAA (S=104S=10^4)3.49 / 953.08 / 950.52 / 954.26 / 954.28 / 1001.70 / 955.23 / 954.57 / 1001.84 / 95
CVaR row-wise (S=103S=10^3)9.20 / 1006.76 / 1005.15 / 1005.75 / 1005.18 / 1003.39 / 954.49 / 1003.85 / 1001.94 / 100
CVaR joint (S=103S=10^3)4.70 / 1002.83 / 1002.00 / 1002.89 / 1002.76 / 1001.68 / 952.58 / 1002.24 / 1001.09 / 85
CVaR row-wise (S=104S=10^4)9.49 / 1006.43 / 1006.57 / 1006.75 / 1006.42 / 1004.77 / 1006.61 / 1006.27 / 1004.68 / 100
CVaR joint (S=104S=10^4)4.98 / 1003.43 / 1002.64 / 1003.64 / 1003.48 / 1002.74 / 1003.85 / 1003.69 / 1003.39 / 100
ACCESS0.00 / 1000.00 / 1000.00 / 1000.00 / 1000.00 / 950.00 / 1000.00 / 1000.00 / 1000.00 / 95

SRCSP

methodSmall α=.90\alpha=.90Small α=.95\alpha=.95Small α=.99\alpha=.99Medium α=.90\alpha=.90Medium α=.95\alpha=.95Medium α=.99\alpha=.99Large α=.90\alpha=.90Large α=.95\alpha=.95Large α=.99\alpha=.99
SAA (S=103S=10^3)1.84 / 950.00 / 1000.00 / 950.00 / 900.98 / 950.79 / 700.07 / 850.28 / 750.41 / 55
SAA (S=104S=10^4)1.74 / 1000.00 / 950.00 / 1000.52 / 1000.09 / 1000.00 / 853.58 / 952.09 / 1000.69 / 95
CVaR row-wise (S=103S=10^3)10.38 / 1007.16 / 1003.10 / 1008.56 / 1006.84 / 1006.95 / 1008.62 / 1007.44 / 1004.62 / 100
CVaR joint (S=103S=10^3)6.93 / 1004.13 / 1000.70 / 1004.53 / 1003.40 / 1002.20 / 1002.65 / 1002.53 / 1002.20 / 100
CVaR row-wise (S=104S=10^4)11.31 / 1007.86 / 1007.92 / 1008.17 / 1007.59 / 1006.73 / 1008.89 / 1007.93 / 1006.47 / 100
CVaR joint (S=104S=10^4)7.51 / 1004.13 / 1002.05 / 1004.62 / 1003.09 / 1003.31 / 1002.60 / 1002.61 / 1002.54 / 100
ACCESS0.00 / 1000.00 / 1000.00 / 1000.03 / 1000.00 / 1000.00 / 1000.04 / 950.00 / 1000.00 / 100

To summarize, the joint formulation roughly halves the FO-gap of the row-wise one, and still trails ACCESS by a clear margin. On the non-Gaussian benchmarks, results are similar and can be provided upon request.

G1. Baselines (continued)

Strengthened SAA formulations. Stronger formulations of the SAA problem exist: mixing-set and star inequalities for random right-hand sides [2, 3], which do not apply to our random-coefficient benchmarks, and branch-and-cut decomposition for general random matrices [4], which does. Strengthened SAA formulations solve the sampled optimization problem faster but do not change the statistical limitation of its optimum: an exact SAA optimum may fit the sampled constraints too closely and remain infeasible out of sample. Importantly, a better SAA incumbent can be less feasible out of sample: objective improvements can come from exploiting the sampled constraints more tightly, producing less conservative solutions with more held-out violations. Faster optimization therefore does not necessarily resolve the feasibility trade-off. The SAA variant was selected for implementation convenience (open-source implementations are often unavailable), generality (our formulation applies to any linear CCSP, regardless of where the uncertainty appears, similar to the vanilla big-M SAA), and because the results would likely not differ significantly for the reason discussed above. That said, we will acknowledge the exclusion as a limitation in the final version of the revised paper.

G2. Random search vs. Bayesian optimization

We ran ACCESS with the search replaced by an equal number of random points, 15 quasi-random points per scenario rather than 5 quasi-random plus 10 BO iterations, on all 1,200 instances with an identical subproblem budget. Below, ACCESS-random denotes this variant. Each cell reports the mean FO-gap (%, lower is better) over the α\alpha-feasible instances / % of the 20 instances α\alpha-feasible on the 10610^6 test scenarios. Bold marks the better gap of the two. Both methods use the standard selection with no adjustments based on δ\delta.

instanceACCESS α=.90\alpha=.90ACCESS α=.95\alpha=.95ACCESS α=.99\alpha=.99ACCESS-random α=.90\alpha=.90ACCESS-random α=.95\alpha=.95ACCESS-random α=.99\alpha=.99
KP Small0.00 / 1000.01 / 1000.00 / 1000.03 / 1000.01 / 1000.07 / 100
KP Medium0.00 / 950.04 / 1000.00 / 1000.01 / 1000.06 / 1000.05 / 100
KP Large0.01 / 1000.01 / 900.00 / 950.06 / 1000.08 / 1000.11 / 90
MWM Small0.00 / 1000.00 / 1000.00 / 1000.00 / 1000.00 / 1000.00 / 100
MWM Medium0.00 / 1000.00 / 950.00 / 1000.00 / 1000.02 / 950.02 / 100
MWM Large0.00 / 1000.00 / 1000.00 / 950.07 / 1000.01 / 1000.03 / 100
SRCSP Small0.00 / 1000.00 / 1000.00 / 1000.00 / 1000.00 / 1000.00 / 100
SRCSP Medium0.03 / 1000.00 / 1000.00 / 1000.03 / 1000.00 / 1000.00 / 100
SRCSP Large0.04 / 950.00 / 1000.00 / 1000.04 / 950.00 / 1000.00 / 100
KP Student-t3t_3 50×50.00 / 1000.01 / 1000.00 / 900.01 / 1000.04 / 1000.03 / 95
KP Student-t3t_3 100×100.00 / 1000.03 / 950.02 / 850.04 / 1000.11 / 1000.03 / 100
KP Jump 50×50.06 / 950.10 / 950.05 / 950.11 / 1000.24 / 1000.24 / 100
KP Jump 100×100.10 / 950.13 / 950.08 / 1000.29 / 1000.31 / 1000.32 / 95
KP Clustered 50×50.14 / 1000.19 / 1000.07 / 900.26 / 1000.24 / 1000.20 / 90
KP Clustered 100×100.09 / 1000.10 / 950.07 / 800.22 / 1000.30 / 1000.29 / 85
KP Risky subset 50×50.05 / 1000.06 / 1000.20 / 1000.30 / 1000.34 / 1000.65 / 100
KP Risky subset 100×100.12 / 1000.20 / 1000.37 / 1000.58 / 1000.65 / 1000.93 / 95

At the same subproblem-solve budget, quasi-random search achieves comparable final objective quality and similar feasibility, confirming that the structured parameterization works well with a lightweight search strategy. It also takes about one-third of the BO search’s wall time on average. BO’s advantage is solve efficiency: it reaches the quality of the full quasi-random run with approximately one-quarter of the subproblem solves. This advantage becomes more valuable as deterministic subproblems become expensive, because solving subproblems outweighs the cost of BO. Overall, these results show that the main gains arise from the structured candidate family and its decoupling from certification, with BO remaining important as a sample-efficient search mechanism, while random search can be effective with lower overhead in simpler problems. We will include these results and a discussion in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.