- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes representing chance constraints through a learned sum-product network (SPN). Training observations consist of decisions, uncertainty realizations, and binary constraint-violation labels. After fitting a joint distribution, the method marginalizes uncertainty and computes the conditional violation probability for a candidate decision. These computations are approximated using refinable piecewise-linear functions and embedded into mixed-integer linear optimization. The authors also derive encoding-error bounds and formulation-strengthening procedures.
The principal motivation is to decouple optimization formulation size from the number of training observations by replacing the chance constraint with a learned surrogate. However, the piecewise-linear encoding introduces substantial auxiliary variables, constraints, and discrete structure, while fitting and compilation incur additional costs. These costs raise concerns about scalability that the experiments on small stochastic knapsack and multi-product newsvendor instances do not resolve. The results demonstrate a proof of concept but do not establish reliable generalization to poorly covered decisions or a compelling practical advantage over alternative learned constraints. Moreover, the experiments do not demonstrate that the tested problems require the large training datasets used, leaving the practical necessity of the proposed approach insufficiently justified.
Critical strengths
-
The formulation enforces numerator and denominator probability computations independently of the optimization objective. Its refinable approximations, propagated encoding-error bounds, and strengthening procedures provide a framework for embedding SPN-based constraints in mixed-integer optimization.
-
The paper distinguishes population feasibility from encoded feasibility and reports unfavorable outcomes, preparation costs, solver time limits, and failures under changed risk limits. This reporting makes the scope and limitations of the evidence assessable.
Critical weaknesses
- The method does not adequately address the statistical and decision-coverage difficulties that determine whether a learned chance constraint is useful.
The paper’s motivation is to avoid formulation growth proportional to the number of observations. This is reasonable; however, the authors do not compare their approach with scenario-reduction techniques to demonstrate its merits. Omitting scenario-reduction techniques cannot identify a convincing regime in which the proposed machinery offers a consequential advantage over existing methods. The paper discusses scenario enforcement and DRO in its related work. These approaches address concerns arising from data scarcity. In contrast, replacing scenarios with a fitted distribution does not itself control epistemic uncertainty arising from limited observations or model misspecification. The derived conservative margins concern encoding error relative to the fitted SPN, rather than estimation error relative to the population distribution; these margins are also not imposed in the reported experiments. More importantly, the main experiments include every legal decision in training: all 1,024 knapsack selections and all 6,039,420 legal newsvendor orders. Newsvendor training additionally targets estimated risk-boundary and high-profit regions. These settings do not establish reliability when optimization selects decisions with insufficient training coverage, a central difficulty in larger decision spaces. A fixed-size formulation does not establish favorable sample complexity or generalization as decision dimension increases. The risk-limit experiments demonstrate that this concern is substantive. At the knapsack’s 1% limit, all three TPM returns are encoded-optimal but population-infeasible. Newsvendor feasibility also deteriorates under changed risk limits. Consequently, the practical significance of the proposed representation remains insufficiently demonstrated beyond the extensively covered primary settings.
- The comparisons do not establish sufficient benefit to justify the additional modeling and encoding machinery.
Separating training-data size from optimization formulation size is not unique to SPNs. Direct probability classifiers can represent a chance constraint through a logit threshold, while deep quantile regression can replace it with a learned quantile inequality. Published DQR work already embeds neural chance-constraint surrogates into mixed-integer linear formulations [1]. These alternatives are missing from the empirical comparison. The reported PWL costs further weaken the demonstrated computational advantage. For knapsack, TPM uses 102,063 variables and 161,987 linear constraints, exceeding SAA-60k on both counts, and additionally uses SOS2 structure. Fitting and compilation add substantial costs. SAA-10k matches TPM’s seven population-optimal knapsack returns with a lower median search time. For newsvendor, SAA-10k is faster and recovers the population optimum in all ten datasets, versus four for TPM.
Reference [1] Ge Chen, Hongcai Zhang, Hongxun Hui, and Yonghua Song. “Deep-Quantile-Regression-Based Surrogate Model for Joint Chance-Constrained Optimal Power Flow With Renewable Generation.” IEEE Transactions on Sustainable Energy, 14(1):657–672, 2023. DOI.
Questions for authors
1 Since the motivation is to avoid optimization formulation growth as the number of observations increases, why are scenario-reduction techniques omitted from the experiments? Can the authors compare against these methods to establish whether the proposed approach offers a computational advantage while maintaining comparable population feasibility and objective quality?
2 Both main experiments include every legal decision in training, and newsvendor training additionally targets estimated risk-boundary and high-profit regions. How does the approach perform when optimization selects decisions in poorly covered or previously unobserved regions? What evidence supports its applicability to high-dimensional problems where exhaustive decision coverage is impractical?
3 How does the method address epistemic uncertainty arising from limited uncertainty observations or model misspecification? The derived margins concern encoding error relative to the fitted SPN, rather than estimation error relative to the population distribution, and are not imposed in the experiments. What evidence supports reliable chance-constraint enforcement when the available observations are insufficient?
4 What advantages does the SPN representation offer over direct feasibility-probability classifiers and DQR surrogates? Can the authors provide comparisons using matched data budgets, accounting for fitting, compilation, and optimization costs, alongside population feasibility and objective quality?
5 Given the substantial auxiliary MILP formulation size and preparation costs, in what regime does PWL refinement provide a practical benefit for large-scale stochastic programming?
6 Why are all three TPM returns population-infeasible at the knapsack’s 1% risk limit despite being encoded-optimal, and why does newsvendor feasibility deteriorate under changed limits? Do these failures primarily arise from estimation error, encoding error, or training coverage concentrated around the original risk boundary?
5 comments
Response 2/3: estimation error and learned baselines (Q3, Q4)
Q3. Estimation error and epistemic uncertainty. We agree that the submitted margins addressed encoding error relative to the fitted SPN, not estimation error relative to the population, and were not imposed experimentally. Our revised pipeline mitigates the consequences of estimation error through improved conditional-risk training (Section 1 of the General response (comment 1/5)) and independent feasibility validation (TPM+), without claiming to quantify epistemic uncertainty in the fitted SPN.
- Estimation and validation: Following the conservative SAA principle of Luedtke and Ahmed (2008), TPM+ solves at , , , and , evaluates each candidate on 100,000 fresh simulator draws, and selects the most profitable one whose one-sided 95% Wilson upper confidence bound is below . At %, raw TPM decisions have true violation probabilities of 5.74–6.12%, exceeding the prescribed limit. TPM+ rejects these candidates and selects alternatives with true risks of 3.71–4.43% across three seeds. Encoding error: The revised nonlinear formulation removes the piecewise-linear approximation, retaining only a conservative numerical clamp relative to the fitted SPN. For MILP-only solvers, the original PWL formulation remains applicable, but its approximation error must still be controlled through the derived margins.
Limitations. This is an empirical safeguard rather than a finite-sample guarantee, and it requires simulator access.
Q4. Classifiers and DQR at matched budgets. We added DQR (Chen et al., 2023) and the linear and ReLU quantile surrogates of Alcántara and Ruiz (2023) to the 50-product newsvendor comparison (Sections 3–4 of the General response (comments 2/5 and 3/5)). All methods use the same 10 million training examples and 200,000 held-out examples. The quantile baselines use the published 3×25 architectures; a DQR capacity check with 3×50 layers improved validation loss by only 1% and still produced an infeasible decision at % (7.91% true risk). The methods did not undergo systematic tuning, unlike TPM.
With validation, TPM+ earns the most among these methods at both risk levels; DQR+ and AR-ReLU+ find no validated decision at %, and AR-Linear+ is always safe but earns 7–12% less. Without validation, DQR and AR-ReLU violate the risk limit in 5 of 6 runs at % and in all 6 at %, and TPM also needs validation at % (Q3). Full results are in the results table in Section 4 of the General response (comment 3/5).
Computational costs. As detailed in Section 4 of the General response (comment 3/5), TPM requires more fitting time than the quantile baselines, but its certified nonlinear solves are substantially faster than those of DQR and AR-ReLU. These baselines generally reach the solver work limit without optimality certificates, whereas AR-Linear fits and solves much faster but produces more conservative decisions. The reported times exclude building the optimization model from the fitted surrogate and simulating the validation draws, which were not recorded separately.
Direct probability classifiers. On the original benchmarks, logistic regression and a ReLU classifier produced feasible decisions. Logistic regression recovered the optimum in all four 30-item knapsack runs, while neither classifier recovered the optimum in ten small-newsvendor runs, with profits 15–25% below optimum. These classifiers were not evaluated on the 50-product newsvendor.
Thus, SPNs offer exact conditional-risk evaluation under the fitted joint model, with one learned model reusable across risk thresholds. The revised results demonstrate an advantage over the tested nonlinear quantile surrogates in validated profit and optimization time, but not a universal advantage over simpler linear surrogates.
Response 3/3: formulation size and the 1% failures (Q5, Q6)
Q5. Formulation size, preparation costs, and regime of benefit. We agree that the submitted PWL formulation incurs substantial overhead. Our revised approach introduces a compact native nonlinear formulation while retaining the explicit PWL encoding for solvers without the required nonlinear capabilities (Section 1 of the General response (comment 1/5)).
-
Formulation size: The revised 10-item knapsack model contains 139 variables, compared with 102,063 in the original PWL-33 formulation, and the revised 50-product newsvendor contains 1,990 (full-model counts). The piecewise-linear encoding adds auxiliary variables for every mixture component and every piece; on the original 5-product newsvendor (PWL-9) this was about 27 variables per component, against 5 with the exact encoding, so the saving grows with the number of components.
-
Solver compatibility: The explicit PWL formulation enables MILP-based optimization without requiring native support for the SPN's nonlinear operations. This is particularly relevant for MILP-only solvers and existing MILP workflows.
-
Comparison with native nonlinear encoding: On the same ten fitted SPNs (a later rerun with new fits), native nonlinear encoding achieved 10/10 optimality certificates versus 9/10 for PWL-33, with lower median solver work (451 versus 1,031 units).
-
Regime of benefit and preparation costs: In the simulation-defined 50-product newsvendor, the revised TPM+ achieves the highest validated profit at % and the best fully validated result at % with certified solves in seconds, while scenario-based and nonlinear quantile alternatives frequently terminate at their work limits (Section 4 of the General response (comment 3/5)).
Overall, the two formulations serve complementary purposes: native nonlinear encoding is faster to solve and more precise, therefore preferred when supported by the solver, whereas explicit PWL encoding enables MILP-based optimization when those nonlinear capabilities are unavailable.
Q6. The 1% feasibility failures in the submission. The original knapsack diagnostics allow us to distinguish estimation from encoding error. At %, all three submitted runs returned the same decision, with true violation probability 1.95%. The fitted SPNs assigned it only 0.65–0.73% risk, while PWL-33 further underestimated risk by 0.13–0.22 percentage points. Thus, SPN estimation error was sufficient to cause the failures: even an exact encoding of those fitted models would have admitted the unsafe decision.
- Revised knapsack results: Improved training and exact nonlinear encoding (see Section 1 of the General response (comment 1/5)) yield feasible decisions in all 16 returned % solutions across 10–50 items, with true risks of 0.01–0.18%. At 100 items, both fitted-SPN optimization problems were certified infeasible. These experiments did not use independent validation.
—
We thank the reviewer again for their constructive feedback. Their comments helped us clarify the distinction between estimation and encoding errors, strengthen the empirical comparisons, and better characterize the regimes in which our approach is useful. We hope the revised evidence and additional analyses address the main concerns, and we would be grateful if the reviewer would reconsider their assessment.
Response 1/3: scenario reduction, coverage and scale (Q1, Q2)
Thank you for your thoughtful and constructive review, particularly for recognizing our distinction between population-level and encoded feasibility, as well as our discussion of the method's limitations. Your questions motivated additional experiments on generalization to unseen decisions, scalability, alternative baselines, and the reliability of learned chance constraints. We address each point below, with further methodological and experimental details provided in the General response.
Q1. Scenario reduction. We have added a scenario-reduction (SR) baseline and expanded the evaluation to the more challenging 50-product newsvendor benchmark introduced in Section 2 of the General response (comment 2/5). We compare raw SR against SR+, which applies the same independent feasibility-validation procedure used for the other methods (Section 3 of the General response (comment 2/5)).
For SR, we cluster N=10,000 sampled scenarios using k-means into M weighted representatives, then solve the resulting SAA formulation using the no-substitution bound.
On the 50-product newsvendor, we obtain:
Expected profit (estimated violation probability), mean ± standard deviation across seeds where applicable. At ε=5%, SR+ statistics cover two of three seeds. † For one TPM+ seed, the 95% simulation-based confidence interval includes ε.
Without validation, SR violates the prescribed risk thresholds at every tested reduction size, with larger violations under more aggressive reduction (at ε=10%, 42% with M=200 and 59% with M=50, one seed). This is consistent with scenario aggregation failing to preserve the tail behavior relevant to the chance constraint.
With validation, SR+ becomes a competitive baseline: at ε=10%, TPM+ achieves higher mean profit; at ε=5%, SR+ achieves comparable profit on two seeds but returns no validated decision on the third. There is also a computational distinction: SR's MILP solves reach their work limits after approximately 15–25 minutes without optimality certification, whereas TPM+'s nonlinear solves are certified in 11–84 seconds.
Q2. Poorly covered decisions and high dimensionality. The submitted experiments did not establish generalization to unseen decisions. We therefore revised SPN training to improve conditional-risk prediction (Section 1 of the General response (comment 1/5)) and evaluated the resulting pipeline in two settings: incomplete training coverage and larger decision spaces.
—
Generalization to unseen decisions. On a 10-item knapsack, we trained models using only 10–50% of possible decisions. Held-out risk-prediction error is 0.7–2.1 percentage points in the current training procedure (compared to ~25 p.p. in the original), and 18 of 27 optimized decisions were unseen during training. On a small newsvendor, excluding the optimal decision and its neighbors from training still allowed recovery of the optimum in 5 of 6 runs using a validation margin.
Scalability. We evaluated the revised pipeline on knapsacks ranging from 10 to 200 items and on a substantially larger, simulation-based newsvendor with 50 integer decision variables and approximately 1072 possible orders. The knapsack experiments allow exact evaluation of feasibility and optimality gaps, while the newsvendor tests optimization over a large decision space without enumeration.
These results support the scalability of the revised approach and its ability to optimize over decisions absent from training. Additional limitations at tighter risk thresholds are discussed in Q6 and the General response.