- 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
-
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.
-
The paper studies three problems under several uncertainty distributions. The reported results suggest that ACCESS can efficiently produce high-quality feasible solutions.
Critical weaknesses
-
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 , , and , the row-wise risk allocation reduces the sample CVaR constraints to enforcing every sampled constraint.
-
The main mathematical result, Proposition 1, follows directly from Hoeffding's inequality and a union bound over a finite candidate set.
-
The paper provides no theoretical guarantee on objective quality, approximation bound, or convergence toward the optimal chance-constrained solution.
Questions for authors
-
Why are stronger approximation algorithms in recent literature not included?
-
Can the authors show any approximation guarantee or convergence result as the number of candidate solutions increases?
-
Proposition 1 shows the feasibility of candidates passing the validation threshold, but does not guarantee that such a candidate exists. How does ACCESS() handle an empty candidate set?
-
How does the performance of ACCESS compare with random or quasi-random sampling of using the same number of subproblem solves?
-
Can the authors report objective bounds or comparisons with best-known optimal values on smaller instances?
3 comments
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 ) on which all 1,024 solutions are enumerated and evaluated on the 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 with a tightened risk level inside the model: the SAA problem requires feasibility on a fraction of the scenarios, for , while the returned solution is still evaluated against the target . Here is standard SAA, and smaller allows fewer violated scenarios and is therefore more conservative (e.g., for , gives ). Every SAA model was solved to optimality. Each cell reports the mean gap to the exact optimum (%) over the -feasible instances / % of instances -feasible / % of feasible instances returning the exact optimum.
| method | |||
|---|---|---|---|
| ACCESS | 0.11 / 100 / 95 | 0.02 / 100 / 95 | 0.00 / 90 / 100 |
| ACCESS() | 0.15 / 100 / 90 | 0.15 / 100 / 90 | 0.55 / 100 / 65 |
| SAA () | 0.89 / 85 / 76 | 0.16 / 80 / 88 | 0.35 / 60 / 83 |
| SAA () | 0.05 / 95 / 95 | 0.21 / 100 / 90 | 0.00 / 80 / 100 |
| CVaR joint () | 4.65 / 100 / 15 | 4.14 / 100 / 5 | 2.26 / 100 / 15 |
| GB | 4.06 / 100 / 15 | 2.30 / 100 / 30 | 1.71 / 100 / 30 |
The next table reports the largest (the least conservative setting) at which SAA is -feasible on every instance, and the gap to the exact optimum it then incurs.
| SAA | |||
|---|---|---|---|
| , 2.25% | , 0.18% | none (95% feasible for ) | |
| , 1.15% | , 0.21% | , 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 (). The cells follow the format of the first table.
| SAA by enumeration | |||
|---|---|---|---|
| 0.00 / 95 / 100 | 0.02 / 95 / 95 | 0.00 / 90 / 100 | |
| 0.00 / 100 / 100 | 0.02 / 100 / 95 | 0.00 / 95 / 100 | |
| 0.00 / 100 / 100 | 0.02 / 100 / 95 | 0.00 / 95 / 100 |
The feasibility of SAA increases steadily with the number of scenarios, and from it essentially recovers the exact optimum, which indicates that its failures at smaller are due to sampling error. The one remaining infeasible instance at has a solution whose feasibility is 0.99001 on the SAA scenarios and 0.98997 on the 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 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 lie on the boundary in the same sense (0.98999 and 0.98997 on the test set). ACCESS() 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 with no value of reaches full feasibility. We note that the value of reported for SAA is selected with knowledge of the test outcome, whereas ACCESS() fixes its margin in advance through . These small instances are favorable to SAA, since it can be solved to optimality with scenarios in minutes. On the instances of the main paper, SAA with reaches the one-hour limit and is infeasible on a quarter of the instances.
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=103 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 N explicit candidates that were generated without the validation scenarios, so the certificate can use 106 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=104), 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.