acceptodds
Under review as a conference paper at ICLR 2027

Representing Uncertainty in Stochastic Programming Using SPNs

Abstract

Optimization under uncertainty is often made tractable by sampling: expectations and chance constraints are replaced by sample-average counterparts via scenario expansion, where meeting stronger statistical requirements may require larger samples and more sophisticated optimization methods. We take a different route and represent uncertainty using a tractable probabilistic model (TPM), specifically a sum-product network learned from data. Its structural properties (smoothness, decomposability) enable exact marginal inference under the fitted model, allowing us to construct conditional probability queries for constraint violations that depend on the decision variables. We represent these queries using refinable piecewise-linear approximations that admit explicit mixed-integer linear formulations. A learned chance constraint thus becomes part of the optimization problem itself, without explicit scenario expansion: for a fixed circuit architecture and encoding policy, additional training observations do not introduce individual optimization attachments. We evaluate the approach on the well-known newsvendor problem and a stochastic knapsack problem, examining how learning and encoding errors affect decision quality and computational cost. The resulting decisions are evaluated for feasibility under the compiled learned constraint and independently assessed against the uncertainty distribution.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
tractable probabilistic models, sum-product networks, chance constraints

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Y5n4OpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  1. 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
AuthorsOpenReview ↗

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,000N = 10{,}000 sampled scenarios using k-means into MM weighted representatives, then solve the resulting SAA formulation using the no-substitution bound.

On the 50-product newsvendor, we obtain:

Methodε=10\varepsilon = 10%ε=5\varepsilon = 5%
TPM+ (ours), 3 seeds2,780 ± 2 (9.7% ± 0.3%)†2,560 ± 23 (4.1% ± 0.4%)
SR+, M=1,000M = 1{,}000, 3 seeds2,739 ± 32 (8.3% ± 0.8%)2/3 validated: 2,559 ± 25 (4.4% ± 0.3%)
SR, M=1,000M = 1{,}000, 3 seedsUnsafe (24.5% ± 0.5%)Unsafe (14.3% ± 0.9%)

Expected profit (estimated violation probability), mean ± standard deviation across seeds where applicable. At ε=5\varepsilon = 5%, SR+ statistics cover two of three seeds. † For one TPM+ seed, the 95% simulation-based confidence interval includes ε\varepsilon.

Without validation, SR violates the prescribed risk thresholds at every tested reduction size, with larger violations under more aggressive reduction (at ε=10\varepsilon = 10%, 42% with M=200M = 200 and 59% with M=50M = 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\varepsilon = 10%, TPM+ achieves higher mean profit; at ε=5\varepsilon = 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 107210^{72} 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.

BenchmarkMain finding
Knapsack, 10–100 items52 of 54 solves returned decisions, all feasible under exact risk evaluation.
Knapsack, 200 itemsAt ε=10\varepsilon = 10% and 5%, all four solves returned feasible decisions within 1% of the proven optima.
50-product newsvendorNone of the optimized orders appeared among the 10 million training examples.

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.

AuthorsOpenReview ↗

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 ε/4\varepsilon/4, ε/2\varepsilon/2, 3ε/43\varepsilon/4, and ε\varepsilon, 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 ε\varepsilon. At ε=5\varepsilon = 5%, 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 ε=5\varepsilon = 5% (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 ε=5\varepsilon = 5%, 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 ε=10\varepsilon = 10% and in all 6 at ε=5\varepsilon = 5%, and TPM also needs validation at ε=5\varepsilon = 5% (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.

AuthorsOpenReview ↗

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 ε=10\varepsilon = 10% and the best fully validated result at ε=5\varepsilon = 5% 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 ε=1\varepsilon = 1%, 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 ε=1\varepsilon = 1% 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.

Reviewer_8GunOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes to use a tractable circuit, SPN, to represent uncertainty for stochastic programming. The method starts with the requirement to generate training data, where the method description explains how it draws both decisions and realizations. While the SPN are tractable, it nonetheless proposes a piecewise-linear approximation.

The method only compares to SAA as a stochastic programming approach, and the figures are visually overwhelming puzzles.

Critical strengths

The use of tractable circuits in optimisation is interesting. Ideally one would do optimisation over the tractable structure though...

Critical weaknesses

Does not compare to SOTA, only to SAA which is a baseline method in stochastic programming.

Figures are unclear: visually overwhelm the reader and do not highlight strenghts/weaknesses of the different methods

technical formulation is a bit all over the place, with no clear choice of the 'key' parts and the 'additional' parts, most technical things are pushed into an appendix and not ablated (max, nr of knots, TPM training data effect; use of cuts...)

it seems the two datasets are handled in a quite different way, casting doubt on the generality of the method

Questions for authors

Please address the weaknesses above

5 comments
AuthorsOpenReview ↗

Response 1/3: baselines beyond SAA and presentation (W1, W2)

Thank you for your review and for recognizing the potential of tractable probabilistic circuits in optimization. We have carefully considered your concerns and conducted additional experiments to strengthen the empirical comparisons, clarify the methodological contributions, and improve the presentation of our results. We address each point below, referring to the General response for additional experimental details.

—

W1. Comparison beyond SAA. We add selected established methods, including those suggested by other reviewers: conservative SAA, scenario reduction (SR), deep quantile regression (DQR), and the linear and ReLU quantile-regression formulations of Alcántara and Ruiz (2023). We extend each with a validation procedure, denoted by appending “+” to the method’s name. We would also welcome any additional references the reviewer considers particularly relevant.

Full results are in the general response. Our approach returns validated decisions across all three seeds at both risk thresholds. At ε=10\varepsilon = 10%, it also achieves the highest mean expected profit among the validated methods. At ε=5\varepsilon = 5%, SR+ achieves comparable profit on its two successful seeds but fails to return a validated decision on the third, while DQR+ and AR-ReLU+ return none.

On the 50-item knapsack, where the chance constraint has a simpler algebraic structure, TPM achieves profits of 787, 777, and 750 at risk thresholds of 10%, 5%, and 1%, respectively, compared with exact optima of 789, 780, and 766. SAA+ and linear quantile regression match or outperform TPM on this benchmark. Together, these results suggest that TPM's advantages are most evident in the more complex, simulation-defined newsvendor setting.

W2. Presentation of results. Thank you for your feedback on the figures. We put considerable effort into presenting the experimental results clearly, but recognize that some visualizations may not have been as easy to interpret as intended. We would appreciate any specific suggestions on which aspects could be improved. We are revising the figures to make the comparisons between methods, risk thresholds, and feasibility outcomes easier to interpret, and plan to upload the revised PDF before the end of the discussion period.

AuthorsOpenReview ↗

Response 2/3: essential components and ablations (W3)

W3. Essential versus optional components. In the submitted experiments, our primary objective was to demonstrate the complete pipeline, from fitting an SPN to embedding its conditional probability queries in an optimization problem. The submitted experiments primarily evaluated the end-to-end formulation, rather than systematically investigating how SPN training affects conditional risk prediction. The expanded experiments highlighted the importance of accurate conditional risk estimation: a model can fit the joint distribution reasonably well while underestimating violation probabilities at decisions selected by the optimizer.

We therefore revised SPN training to prioritize conditional risk prediction while retaining joint probabilistic modeling. The revised procedure combines gradient-balanced training, decision leaves that reflect the structure of the variables, and a training distribution designed to cover relevant regions of the decision space. These changes, together with the optimization encoding and independent feasibility validation, constitute the revised pipeline described in Section 1 of the General response (comment 1/5).

Several components the review lists (the number of knots, the training data and the cuts) were ablated in the appendix of the submission, but we did not signpost these results well. We summarize them below, after the new ablations. Newsvendor ablations use one seed.

Revised pipeline (new experiments).

ComponentEffect of modification or removal
Ordinal decision leavesReplacing them with categorical leaves produces orders with 23% true risk at ε=10\varepsilon = 10% and 27% at ε=5\varepsilon = 5%; TPM+ returns no validated decision.
Gradient-balanced training (α=0.03\alpha = 0.03)Increasing α\alpha to 0.1 produces an order with 37% true risk at ε=10\varepsilon = 10%.
Mixture componentsIn a separate knapsack capacity study (10% decision coverage, joint-loss weight λ=0\lambda = 0), K=16K = 16 yields 1.7–3.0 percentage points of near-threshold held-out error, versus 6.8–10.7 for K=64K = 64 across three seeds.
Structure-informed samplingGeneric sampling covers substantially fewer low-risk orders (0.75% versus 17.8% with true risk ≤ 5%). TPM+ finds no validated decision at ε=5\varepsilon = 5% with generic sampling.
Independent validation (+)Without validation, TPM returns decisions with 5.9% ± 0.2% true risk at ε=5\varepsilon = 5%, exceeding the prescribed threshold.
Native nonlinear encodingOn the same 10 fitted knapsack SPNs (10 items), exact encoding certifies 10/10 against 9/10 for 33-piece PWL, with less than half the solver work (median 451 vs. 1,031 work units).

Original PWL pipeline (appendix of the submission). The PWL encoding remains the option for solvers without native nonlinear constraints: it uses only linear constraints and integer variables, so these results apply whenever the problem must be solved as a MILP.

ComponentEffect of modification or removal
Number of knotsOn unchanged fits, PWL-9/17/33 reduce the knapsack encoding error from 0.54 to 0.17 and 0.08 percentage points, and raise truly feasible knapsack decisions from 7/10 to 10/10; newsvendor orders are identical at all three resolutions, while the formulation grows from about 28,000 to 69,000 variables ("Encoding fidelity and resolution sensitivity").
Training-data sizeKnapsack risk error falls from 21.3 to 3.2, 1.0 and 0.8 percentage points from 10k to 3.7M rows (three replicates each); at 1M rows all three returned decisions are feasible, and the formulation size is unchanged ("Data-size and model-capacity results").
Circuit-derived cutsIn matched pairs, cuts tighten all six bounds and yield four optimality certificates versus none without them. The revised nonlinear pipeline does not need them.

The maximum shift in the log-sum-exp, used by both pipelines, is an exact identity for numerical stability; it does not change the constraint, so we did not ablate it.

AuthorsOpenReview ↗

Response 3/3: consistency across benchmarks and the PWL encoding (W4, W5)

W4. Consistency across benchmarks. In the submitted experiments, the newsvendor used targeted sampling around estimated risk boundaries, whereas the knapsack used a different training design. We have since revised the methodology to use a common pipeline across both benchmarks: gradient-balanced training with α=0.03\alpha = 0.03, decision-leaf regularization appropriate to each variable type, native nonlinear encoding, and independent simulation-based validation on the newsvendor (knapsack decisions are evaluated exactly).

Some choices remain problem-specific because the decision spaces differ. We use binary leaves for the knapsack and ordinal leaves for the newsvendor, with 32 and 128 mixture components, respectively. Training decisions are sampled uniformly for the knapsack, while the newsvendor uses a fixed, structure-informed sampling design based on its order caps and budget, without preliminary risk estimates. These choices adapt the shared methodology to each problem rather than introducing separate optimization pipelines.

W5. Why use piecewise-linear approximation if SPNs are tractable? Tractability of SPNs refers to probabilistic inference, not optimization over their inputs. Although conditional violation probabilities can be evaluated efficiently for a fixed decision, imposing them as constraints introduces nonlinear, generally nonconvex expressions involving the decision variables.

The piecewise-linear formulation in the submission was designed to make these constraints compatible with MILP solvers, rather than being a requirement of SPN inference. In the revised experiments, we instead use Gurobi 13.0.2's native nonlinear constraints, eliminating the approximation and its associated auxiliary variables. The original piecewise-linear formulation remains an alternative for MILP-only solvers, with controllable approximation error. Further details are provided in Section 1 of the General response (comment 1/5).

—

We thank the reviewer for their suggestions, which led to the strengthening of the paper and new insights. We hope the additional baselines, ablation studies, and methodological clarifications address your main concerns and provide a stronger basis for evaluating our contribution. We welcome further feedback and would appreciate your reconsideration of the paper's assessment and score in light of these new results.

Reviewer_FtyNOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a learning-based approximation for chance-constrained stochastic programming (CCSP). Specifically, the authors use a sum-product network (SPN) to learn decision violation probabilities, then represent these SPN approximations as piecewise-linear constraints in a mixed-integer linear program (MILP) to make decisions that approximately satisfy the underlying chance constraint. On two synthetic benchmarks, they show that their method computes high-quality solutions that are feasible in nearly all cases.

Critical strengths
  • Motivation: Overall, the paper and method are well motivated, and to the best of my knowledge, this is the first approach to leverage tractable probabilistic models for optimization surrogates, rather than surrogates based on feed-forward network-based function estimation. This is consequential because it offers a novel approach and a new perspective in the area.
Critical weaknesses

While the paper has some methodological innovation, the computational experiments are far too limited.

  • Benchmarks & Scalability: The authors test on two synthetic instances that are extremely small, i.e., 5 and 10 binary decision variables, that only have a single chance constraint. Moreover, even on these small instances, the method is instance-specific and requires significant time for data collection, training, and compilation, plus substantial search time, raising concerns about its advantages over the SAA baseline and its scalability to more realistic problems. Even the results in the appendix point toward a requirement for a large amount of data and a large number of pieces to better approximate the SPN, both of which may become prohibitive in larger problem settings.

    To improve the work, I suggest the authors include (1) larger benchmarks, e.g., on the order of tens to hundreds of decision variables at least, (2) evaluate their method on single and joint-chance constraints, and (3) include other baselines, e.g., CVaR and a closely related method [1] (which approximates the quantile-based reformulation using ReLU networks, not cited or discussed). Without these, I believe the authors have not established any points regarding scalability or benefits over existing methods, so I believe this is a clear rejection.

  • Amortization and Leakage: The method itself suffers from two major limitations. First, it is instance-specific; for example, all the time spent collecting data and training yields a model usable only on a single instance, which is a severe limitation. If either the setup cost were substantially lower, or the learned model could be used across instances from some distribution (the standard learning-to-optimize framing), then there would be a more reasonable justification. The second issue is leakage between the training data and the downstream decision. The authors use millions of decisions for their training data. However, because the method is instance-specific, it will almost certainly overlap with the training data and the optimized decision (or at least an overwhelming portion of the search space). For this reason, I don't believe there is any evidence of generalization beyond the training data, so the authors could just enumerate all decisions and check instead of training a model and optimizing over it. This is consequential, as it calls into question the method's usefulness.

Questions for authors
  • Compared to [1], is there any advantage of the proposed method? [1] doesn't require any piecewise approximation (only exact ReLU piecewise representations), so I don't see much of an advantage over this existing approach that the authors did not cite.
  • It was a bit hard to infer from the text, but is the training data indeed essentially covering the entire decision space?
  • The authors don't clearly state what (if any) part of the MILP representation of the SPN is novel in this work. Can the authors more clearly delineate which components of the MILP modeling of the SPN are actually novel?

References

  • [1] Antonio Alc´antara and Carlos Ruiz. On data-driven chance constraint learning for mixed-integer optimization problems. Applied mathematical modelling, 121:445–462, 2023.
4 comments
AuthorsOpenReview ↗

Response 1/2: scalability, cost and generalization (W1, W2, W4, Q2)

Thank you for your careful review and for recognizing the potential of tractable probabilistic models as optimization surrogates. We acknowledge your concerns regarding scalability, computational cost, and generalization, and have conducted additional experiments to address them.

—

Scalability and computational cost (W1, W2). We introduce a 50-product newsvendor benchmark with approximately 107210^{72} possible decisions and a simulation-defined chance constraint. We also extend the knapsack experiments to 200 decision variables. Using Gurobi's native nonlinear constraints, the newsvendor formulation has 1,990 variables and solves in 11–84 seconds, with all six runs certified globally optimal for the fitted SPN.

The main cost is training: TPM requires 10 million simulation samples and 41 minutes of GPU fitting. However, its optimization takes only 16–36 seconds on average, compared with 27–38 minutes for DQR and AR-ReLU, whose solves rarely reach an optimality certificate. AR-Linear fits and solves much faster, but yields lower profits on the newsvendor. These times exclude data generation.

On the 50-product newsvendor, TPM+ attains the highest validated expected profit at ε=10\varepsilon = 10% (2,780, within 1% of the best-known order) and returns validated decisions on every seed at ε=5\varepsilon = 5% (2,560), matched only by scenario reduction with validation on two of three seeds. AR-Linear is always safe but earns 7–12% less, and AR-ReLU is unsafe without validation. Full results are in Section 4 of the General response (comment 3/5).

Leakage and generalization (W4, Q2). Our original experiments focused on optimizing with a fitted SPN, without explicitly evaluating generalization to unseen decisions. We now address this with the 50-product newsvendor benchmark, which has approximately 107210^{72} possible decisions. Although the SPN is trained on 10 million simulated samples, none of the optimized orders appear in the training data. We also improve training through a conditional-risk objective, ordinal decision distributions, and sampling that covers both the broader decision space and the region near the budget constraint. See details in the general response.

As an additional check, we evaluate prediction accuracy on the 10-item knapsack with only 10–50% of decisions included in training. The mean absolute error on unseen decisions is 0.7–2.1 percentage points. Under the original training procedure, this was 22–28 p. p.

AuthorsOpenReview ↗

Response 2/2: instance specificity, Alcántara and Ruiz, novelty, joint constraints (W3, Q1, Q3, W2)

Instance specificity (W3). TPM fits an SPN for each problem instance, reflecting its uncertainty distribution and decision space. Different instances may involve different distributions, constraints, and decision variable types (binary, categorical, or ordinal), making direct reuse of the same model inappropriate in general. Importantly, within an instance, a single well-fitted SPN supports any risk threshold ε\varepsilon without retraining. Q1. Comparison with Alcántara and Ruiz (2023). We have added their linear and ReLU quantile-regression methods as baselines. On the 50-product newsvendor, TPM+ achieves 13% higher expected profit than AR-Linear at ε=10\varepsilon = 10% and 8% higher at ε=5\varepsilon = 5%. AR-ReLU produces decisions that violate both risk thresholds without validation; with validation, it achieves lower profit at 10% and finds no acceptable decision at 5%. In contrast, AR-Linear performs better on the 50-item knapsack, where the chance constraint has a simple algebraic structure.

Beyond these results, TPM offers two structural advantages. First, a single fitted SPN supports multiple risk thresholds, whereas the quantile-regression approach requires fitting a model for each target risk level. Second, TPM learns from binary violation labels, without requiring a continuous violation margin. In addition, our revised formulation likewise avoids the piece-wise approximation by using the optimizer's native nonlinear constraints.

Q3. Novelty of the optimization formulation. Our contribution is not a generic MILP encoding of SPNs, but a framework for turning their conditional probability queries into optimization constraints. Compared to prior work on encoding the SPN structure, we propose approximating the log-sum-exp with a piecewise function or using a solver’s native function instead of a max function. We derive propagated bounds and callback cuts that exclude infeasible decisions or certified infeasible groups of decisions while preserving the compiled feasible set. These cuts have measurable benefits: in matched experiments, they tighten solver bounds and improve optimality certification. Joint chance constraints and CVaR (W2). Our experiments focus on individual chance constraints to isolate the effects of learning and embedding the violation probability. The framework can also represent a joint chance constraint by defining the violation label as the event that at least one constraint is violated, although we have not evaluated this extension experimentally. CVaR, on the other hand, requires modeling the magnitude of losses rather than only their probability. We therefore leave its treatment outside the scope of the present work.

—

We hope these additional experiments and clarifications address your main concerns regarding scalability, generalization, and methodological novelty. If so, we would appreciate your reconsideration of the paper's assessment and score.

Thanks for the additional experiments. Overall, the larger benchmark does give more confidence. However, I have a few remaining concerns:

  • The risk-tuned (+) variants: The way ϵ\epsilon is adjusted is probably too aggressive (e.g., with an original ϵ=10\epsilon=10%, the closest risk-tuned variant is 3ϵ/43\epsilon/4, but this is already probably overly conservative, whereas a factor like 9ϵ/109\epsilon/10 or even greater may have a much better trade-off. If the authors have a more detailed analysis of the objective/feasibility trade-off across each risk-tuned level, that might be informative.
  • Instance-specific cost and amortization. The authors state that while their training time is significant, the solving time is small, which is fair. However, the fitting cost remains instance-specific and substantial, so the practical advantages are unclear. It would be useful for the authors to consider the approach's performance in lower-data regimes; e.g., an ablation from 1000 samples to 10 million might better assess the method's potential practical use cases. Moreover, given the current number of samples and how they are drawn, it might be reasonable to report how much the method improves upon this pool of solutions.
AuthorsOpenReview ↗

Follow-up: finer candidate grid, smaller training budgets, smaller model and the training pool

Thank you for taking the time to engage with our response and for the constructive suggestions. We are glad the larger benchmark gives more confidence, and we ran the three analyses you proposed (50-product newsvendor, 3 seeds).


Granularity of the (+) variants. Candidates at nine limits, each validated with the same rule (mean over seeds; "passes": seeds whose 95% bound is below ε):

Candidate limitε = 10%: profit (validated risk)passesε = 5%: profit (validated risk)passes
0.5ε2,657 (5.9%)3/3none
0.6ε2,697 (6.9%)3/32,348 (2.1%)3/3
0.7ε2,725 (7.7%)3/32,521 (3.6%)3/3
0.75ε2,737 (8.0%)3/32,560 (4.1%)3/3
0.8ε2,747 (8.4%)3/32,588 (4.6%)2/3
0.85ε2,756 (8.8%)3/32,611 (5.0%)1/3
0.9ε2,765 (9.2%)3/32,629 (5.5%)0/3
0.95ε2,772 (9.3%)3/32,644 (5.6%)0/3
ε2,780 (9.6%)3/32,657 (5.8%)0/3

At ε = 10% TPM+ already selects ε. At ε = 5% you are right: the finer grid raises TPM+ from 2,560 to 2,590 (all seeds confirmed below 5%), within 0.4% of the best-known order. Since the baselines used four levels, we keep those in the main comparison. Note that this study was nearly free for TPM: one fitted model serves every level, at a solve of seconds each, whereas quantile methods need a model (or refit) per level and SAA/SR a new 15–35-minute solve.


Lower-data regime. Profit (true risk) when TPM is fitted on fewer rows; "none" = no decision:

Training rowsTPM, ε = 10%TPM+, ε = 10%TPM, ε = 5%TPM+, ε = 5%
1,0003,032–3,127 (53–67%)none (3/3)1 of 3: 2,985 (48%)none (3/3)
10,0002 of 3: 3,036–3,087 (38–43%)none (3/3)none (3/3)none (3/3)
100,000none (3/3)none (3/3)none (3/3)none (3/3)
1,000,0002,838–2,846 (13.2–13.3%)2 of 3: 2,598 (5.4%), 2,353 (2.2%)2 of 3: 2,598 (5.4%), 2,353 (2.2%)1 of 3: 2,353 (2.2%)
10,000,0002,780 ± 2 (9.7%)2,780 ± 2 (9.7%)2,657 ± 7 (5.9%)2,560 ± 23 (4.1%)
SAA+ (1,000 scenarios)2,559 ± 25 (4.4%)2,358 ± 26 (2.4%)

As expected for a probabilistic model, TPM is data-hungry: at K = 128 it needs about 10 million samples to beat SAA+ (both TPM+ and SAA+ also validate on 400,000 fresh draws, so at 100,000 training rows their simulator budgets are comparable, about 0.5 and 0.4 million). With more data, its risk estimates converge, and at every budget TPM+ fails safe (validation rejected all unsafe orders, up to 67% true risk). The approach thus suits applications where uncertainty samples are abundant, such as inventory and logistics planning with historical demand and order records, or power-system expansion planning (deciding which generation, storage and transmission capacity to build under uncertain demand and renewable output) with years of load and renewable profiles. Since the fitted model remains valid as long as the uncertainty and the violation event are unchanged, it also suits repeated decisions where only deterministic data (prices, costs, budgets) change, where fast certified solves pay off.

Smaller model. The runs above fix the model size at K = 128. Since smaller models fit better from little data on the knapsack, we refitted with K = 16 (3 seeds); profit (true risk), "none" = no decision:

Model (training rows)TPM, ε = 10%TPM+, ε = 10%TPM, ε = 5%TPM+, ε = 5%
K = 16 (100,000)2,960–3,077 (26–35%)none (3/3)2 of 3: 2,949–2,961 (23–27%)none (3/3)
K = 16 (1,000,000)2,780 ± 14 (9.3%)2,780 ± 14 (9.3%)2,620 ± 26 (5.1%)2,582 ± 39 (4.5%)
K = 128 (1,000,000)2,838–2,846 (13.2–13.3%)2 of 3: 2,598 (5.4%), 2,353 (2.2%)2 of 3: 2,598 (5.4%), 2,353 (2.2%)1 of 3: 2,353 (2.2%)
K = 128 (10,000,000)2,780 ± 2 (9.7%)2,780 ± 2 (9.7%)2,657 ± 7 (5.9%)2,560 ± 23 (4.1%)

With 10 times less data and a 19-minute fit instead of 41, K = 16 matches K = 128 on 10 million rows, and even without validation its true risk stays close to the limit. The data requirement thus depends largely on model capacity; at 100,000 rows, K = 16 still returns no validated decision.


Improvement over the training pool. As a baseline without optimization, we took the ~10 million orders sampled for training and searched for the most profitable one that passes the same validation. The sampled orders are either profitable but unsafe, or safe but much less profitable: the best one we found passes validation at both risk levels (true risk 3.5% on 10⁶ draws) and earns 2,404. TPM+ earns 2,780 at ε = 10% and 2,560 at ε = 5%, i.e., 16% and 6.5% more, so optimizing over the fitted model finds better orders than any it was trained on.


We hope these analyses address your suggestions and can inform your final assessment. Thank you again for your engagement throughout the discussion.

Comments on the paper

6 comments
AuthorsOpenReview ↗

General response (1/5): overview and improved training

We thank the reviewers for their feedback. We have substantially expanded the experimental evaluation to address the central concerns regarding scalability, competitive baselines, and generalization. The new evidence is summarized below.

ConcernRaised byWhat we did
Doubts on the training process and the generalizationFtyN, 8Gun, Y5n4Improved SPN training, held-out decision evaluation, and independent feasibility validation
Limited scale of benchmarksFtyN, Y5n450-product newsvendor with ∼1072\sim 10^{72} possible orders
Insufficient baselinesFtyN, 8Gun, Y5n4Added conservative SAA, scenario reduction, DQR (Chen et al. 2023), Alcántara and Ruiz (2023)

All results reported below are new. We are currently incorporating them into a revised manuscript, which we will upload during the discussion period with changes highlighted. We present the results here first to address the reviewers' concerns without delaying our responses.

1. Improved SPN training

These changes refine the original method rather than replace it, and they make possible what the submission could not: accurate risk prediction on decisions absent from training (held-out error 0.7–2.1 points, against 22–28 before), problems with about 107210^{72} decisions, and an exact chance constraint solved to global optimality in seconds instead of a piecewise-linear approximation.

Preventing optimizer exploitation. Optimizing against a learned chance constraint can amplify prediction errors: the optimizer may select profitable decisions whose risk is underestimated. We revised SPN training to improve conditional risk prediction while retaining joint uncertainty modeling.

Gradient-balanced training. We minimize

L=Lcond+λLjoint,λ=α∥∇θLcond∥∥∇θLjoint∥,α=0.03\mathcal{L}=\mathcal{L}_{\text{cond}}+\lambda\mathcal{L}_{\text{joint}}, \quad \lambda=\alpha\frac{\lVert\nabla_{\theta}\mathcal{L}_{\text{cond}}\rVert}{\lVert\nabla_{\theta}\mathcal{L}_{\text{joint}}\rVert}, \quad \alpha=0.03

The conditional loss prioritizes violation prediction, while the joint loss preserves probabilistic modeling of decisions and uncertainty. We balance their gradient contributions over shared parameters at each minibatch, preventing joint likelihood training from dominating conditional risk prediction. Too much weight on the joint likelihood sharply degrades risk prediction: on the 10-item knapsack, fixed weights of 0.1 and 1 raise the near-limit held-out error from about 2 to 9–37 points, and on the newsvendor, α=0.1\alpha = 0.1 instead of 0.03 yields an order with 37% true risk (training ablations, Section 4). Balancing keeps the joint term at a fixed fraction α\alpha of the conditional gradient, so one setting (α=0.03\alpha = 0.03) carries over across problems whose likelihood scales differ; in our sweeps it matches the best fixed weights.

Ordinal decision leaves. We replace categorical leaves with beta-binomial distributions, a standard model for bounded count variables (Johnson et al., 2005). Their two-parameter representation captures ordinal structure and shares information across neighboring quantities, while a 2% uniform floor keeps every decision's probability positive, so the conditional risk stays well-defined and finite for decisions never seen in training, which matters for the poorly covered decisions raised by Reviewer Y5n4. The floor was not ablated separately. Replacing these leaves with categorical ones yields orders with 23–27% true risk (Section 4).

Structure-informed sampling. We sample training orders using only the order caps and budget, with half drawn across a broad range of quantities and half concentrated near full budget utilization. Unlike our original approach, this requires neither preliminary risk estimates nor optimized solutions. We selected this distribution after initial experiments and use the same training data for all learned baselines. It places 17.8% of training orders at true risk ≤ 5%, against 0.75% for a generic design (Section 4).

Optimization encoding. The SPN chance constraint can be embedded directly using a solver's native nonlinear constraints, avoiding the auxiliary variables introduced by our original piecewise-linear (PWL) formulation. With Gurobi 13.0.2, the resulting formulation has 1,990 variables and solves the fitted-SPN optimization problem to global optimality in 11–84 seconds. For comparison, our original piecewise-linear encoding of the 5-product newsvendor needed about 28,000 variables, 27,800 of them auxiliary to the chance constraint (about 27 per mixture component, against 5 now), plus 78,000 linear rows and 2,050 SOS constraints. On the same fitted knapsack SPNs, the exact encoding certified 10/10 solves against 9/10 for PWL-33, with less than half the solver work. For solvers without suitable nonlinear support, the PWL formulation remains available with controllable approximation error.

AuthorsOpenReview ↗

General response (2/5): benchmark and baselines

2. A more challenging benchmark

We introduce a substantially larger, simulation-based newsvendor benchmark with approximately 107210^{72} possible orders, beyond the reach of enumeration.

ComponentSpecification
Decision variables50 integer order quantities
Decision domain0–12 to 0–40 units per product
Product structure10 substitution groups
UncertaintyCorrelated, overdispersed demand; random arrival order
Product substitutionWithin-group, probability 0.45 (Gruen, Corsten and Bharadwaj 2002)
Chance constraintProbability of more than 32 lost units ≤ ε\varepsilon

Unlike the original benchmarks, constraint violations depend on random customer arrival order and probabilistic product substitution. This makes the chance constraint simulation-defined rather than directly available in algebraic form. On this benchmark, TPM+ returns validated decisions on every seed at ε=10\varepsilon = 10% and 5%, within 1–1.5% of the best-known orders (Section 4).

3. Methods and baselines

SAA as the main baseline. SAA is our primary statistical baseline, with established asymptotic convergence guarantees under suitable assumptions (Luedtke and Ahmed, 2008; Pagnoncelli, Ahmed and Shapiro, 2009). The table below summarizes the methods considered and their differences.

Learned baselines. DQR (Chen et al., 2023) fits one ReLU network that predicts several quantiles of the continuous violation margin (here, lost units minus the threshold) as a function of the decision; the chance constraint becomes "predicted (1 − ε\varepsilon)-quantile ≤ 0", and the network is embedded in the MILP with a standard big-M encoding. AR (Alcántara and Ruiz, 2023) fits one quantile model per risk level, either linear (AR-Linear) or a ReLU network (AR-ReLU), embedded the same way. Both use the papers' 3×25 ReLU architectures and the same 10 million training rows as TPM.

Conservative validation. Following the conservative SAA principle (Luedtke and Ahmed, 2008), we generate candidates at ε/4\varepsilon/4, ε/2\varepsilon/2, 3ε/43\varepsilon/4, and ε\varepsilon. Each is evaluated using 100,000 fresh simulations, and we retain the most profitable candidate whose one-sided 95% confidence bound on violation probability is below ε\varepsilon. We denote these variants with “+” (e.g., TPM+, SAA+, SR+).

MethodPer-scenario constraintReusable across ε\varepsilonRequired information
TPM (ours)Not requiredYes, re-solve onlyUncertainty samples and violation labels
SAARequired*Yes, re-solve onlyScenarios
SR (scenario reduction)Required*Yes, re-solve only (the clustering does not depend on ε\varepsilon)Scenarios
DQR (Chen et al., 2023)Not requiredFor risk levels fixed before trainingContinuous outcomes
AR (Alcántara and Ruiz, 2023)Not requiredNo, one model per risk levelContinuous outcomes

* For SAA and SR, per-scenario constraints use algebraic approximations of lost sales: no substitution provides an upper bound, while full within-group pooling provides a lower bound. The simulator-defined constraint is not directly available in algebraic form.

AuthorsOpenReview ↗

General response (3/5): results on the 50-product newsvendor

4. Results on the 50-product newsvendor

We impose a capacity budget of 2,600, limiting the total space occupied by ordered products. This budget creates a meaningful trade-off between profit and risk at ε=10\varepsilon = 10% and 5%. We also report the best-known orders found through a separate search as reference values, not proven global optima.

Methodε=10\varepsilon = 10%ε=5\varepsilon = 5%
Best-known order (reference)2,809 (10.0%)†2,600 (4.9%)
TPM+ (ours)2,780 ± 2 (9.7% ± 0.3%)†2,560 ± 23 (4.1% ± 0.4%)
TPM (ours)2,780 ± 2 (9.7% ± 0.3%)†Unsafe (5.9% ± 0.2%)
DQR+2,710 ± 25 (8.6% ± 0.7%)No decision
DQR1/3 feasible: 2,684 (7.9%); 2/3 unsafe (10.3% ± 0.2%)Unsafe (7.4% ± 0.5%)
AR-ReLU+2,738 ± 13 (9.0% ± 0.6%)No decision
AR-ReLUUnsafe (12.0% ± 0.9%)Unsafe (8.2% ± 0.5%)
AR-Linear+2,455 ± 0 (5.2% ± 0.1%)2,370 ± 3 (3.8% ± 0.1%)
AR-Linear2,455 ± 0 (5.2% ± 0.1%)2,370 ± 3 (3.8% ± 0.1%)
SAA+2,559 ± 25 (4.4% ± 0.3%)2,358 ± 26 (2.4% ± 0.2%)
SAA (pooled)Unsafe (31.9% ± 0.7%)Unsafe (22.1% ± 0.4%)
SR+2,739 ± 32 (8.3% ± 0.8%)2/3 feasible: 2,559 ± 25 (4.4% ± 0.3%)
SRUnsafe (24.5% ± 0.5%)Unsafe (14.3% ± 0.9%)

Entries report expected profit (estimated violation probability), as mean ± standard deviation over three seeds unless otherwise indicated; † marks a result whose 95% interval contains ε\varepsilon. “Unsafe” means estimated risk exceeds ε\varepsilon; “No decision” means no validated feasible decision was returned. SAA uses 1,000 scenarios, and SR uses 1,000 representative scenarios. SAA+ uses the conservative no-substitution bound, while SAA uses the full-pooling lower bound. AR denotes Alcántara and Ruiz; SR denotes scenario reduction.

Computational costs. The table reports mean optimization times across three seeds at each risk threshold (ranges in parentheses), alongside GPU fitting times and the number of solves certified optimal for each method's formulation.

MethodFitting (GPU)Solve time, ε=10\varepsilon = 10%Solve time, ε=5\varepsilon = 5%Certified solves
TPM (ours)41 min16 s (12–18)36 s (11–84)6/6
DQR0.6 min38 min (32–43)33 min (26–44)0/6
AR-ReLU1.7 min (AR-ReLU+: 4.3 min)27 min (10–46)35 min (19–44)1/6
AR-Linear0.5 min (AR-Linear+: 1.4 min)<1 s<1 s6/6
SAA, no substitution (N=1,000N = 1{,}000)—19 min (13–23)29 min (17–37)0/6
SAA, full pooling (N=1,000N = 1{,}000)—25 min (23–26)25 min (21–27)0/6
SR (M=1,000M = 1{,}000)k-means20 min (15–24)17 min (17–18)0/6

Times exclude simulator data generation and are not end-to-end costs. AR fits one model per quantile level, so its validated variants must refit 10 models to cover the candidate levels (ε/4\varepsilon/4 to ε\varepsilon for each ε\varepsilon); TPM and DQR fit a single model for all levels. The quantile networks are small (3×25 ReLU, about 2,600–2,800 parameters) and were trained on the same 10 million rows for 6,000 steps, twice TPM's, with checkpoint selection on held-out data; doubling DQR's width to 3×50 improved its validation loss by only 1%. Their long solve times come from the big-M MILP encoding of the ReLU units, whose relaxation is weak, not from model size. TPM fitting was re-timed on an otherwise idle GPU; each of the three seeds took 41 minutes. Certification refers to global optimality of each method's encoded optimization problem, not the true population problem.

Main findings. TPM+ returns decisions within the risk limit on all seeds at ε=10\varepsilon = 10% and 5% (one at the limit at 10%, marked †), achieving expected profits within approximately 1–1.5% of the best-known orders and 8.6% above conservative SAA at both risk limits. SR+ is competitive at ε=10\varepsilon = 10%, but at ε=5\varepsilon = 5% returns feasible decisions in only two of three seeds. DQR+ and AR-ReLU+ return no validated feasible decision at ε=5\varepsilon = 5%.

Tighter risk threshold. At ε=1\varepsilon = 1%, no evaluated method returns a validated feasible decision. A dedicated simulator-guided search found no order below 1.41% risk (95% CI 1.38–1.43%). We cannot determine whether the problem is infeasible at this threshold.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.