arxiv: 2605.14494 · v1 · submitted 2026-05-14 · 💻 cs.AI · cs.LG

Recognition: unknown

Learning Scenario Reduction for Two-Stage Robust Optimization with Discrete Uncertainty

Tianjue Lin , Jianan Zhou , Jieyi Bi , Yaoxin Wu , Wen Song , Zhiguang Cao , Jie Zhang

Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:00 UTC · model grok-4.3

classification 💻 cs.AI cs.LG

keywords scenario reductiontwo-stage robust optimizationneural surrogateimitation learningGNN-Transformerdiscrete uncertaintylookahead heuristicrecourse cost

0 comments

The pith

A GNN-Transformer trained to imitate a lookahead heuristic selects reduced scenarios for two-stage robust optimization while matching quality at 7-200x higher speed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Two-stage robust optimization becomes intractable when the uncertainty set contains too many discrete scenarios, so scenario reduction is needed to keep computation feasible. The paper first builds PRISE, a sequential method that picks scenarios by measuring their marginal effect on the recourse cost through repeated subproblem solves. Because this lookahead is expensive, the authors train NeurPRISE, a GNN-Transformer that learns to rank scenarios by imitating PRISE's choices with a gain-aware objective. If the surrogate preserves selection quality, practitioners can solve much larger robust problems quickly without solving every subproblem at inference time.

Core claim

PRISE builds reduced scenario sets by sequentially evaluating the marginal impact of each candidate scenario on the recourse cost via lookahead subproblem solves. NeurPRISE replaces the expensive evaluations with a GNN-Transformer that encodes individual scenario structure through graph convolution and cross-scenario dependencies through attention, then scores scenarios with a learned ranking function trained by imitation learning on PRISE selections. On three 2RO benchmark problems the resulting reduced sets produce solutions whose regret stays competitive with full-set and comprehensive baselines.

What carries the argument

GNN-Transformer backbone that encodes per-scenario structure via graph convolution and captures interactions via attention, trained to score marginal gains for sequential selection.

If this is right

NeurPRISE produces reduced scenario sets whose regret is competitive with using all scenarios or other reduction methods.
The method scales to larger numbers of scenarios and runs 7-200 times faster than PRISE.
The trained model generalizes zero-shot to instances up to 5 times larger in scale and 4 times more scenarios.
Scenario reduction becomes practical for 2RO problems that were previously limited by computation time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same imitation-learning approach could be applied to accelerate scenario reduction in other stochastic or robust optimization families not tested here.
If the surrogate generalizes reliably, it could support repeated re-optimization in settings where uncertainty realizations arrive online.
Pairing NeurPRISE with a post-processing exact solve on the reduced set might yield hybrid algorithms that trade a small amount of optimality for large speed gains.

Load-bearing premise

The marginal impact of each scenario on recourse cost can be approximated accurately enough by a model trained only on PRISE's selections, without re-solving subproblems at inference time, and that this approximation holds across scales and distributions.

What would settle it

Run NeurPRISE and the full set on a fresh 2RO instance drawn from a shifted distribution; if the objective gap exceeds the gap produced by PRISE by more than a small constant factor, the learned surrogate does not preserve quality.

Figures

Figures reproduced from arXiv: 2605.14494 by Jianan Zhou, Jieyi Bi, Jie Zhang, Tianjue Lin, Wen Song, Yaoxin Wu, Zhiguang Cao.

**Figure 2.** Figure 2: Empirical analysis of PRISE on small-scale instances. (a) Marginal gains empirically [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

**Figure 3.** Figure 3: Constraint–variable bipartite graph for a scenario MILP (SEL/VC), where variables form [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

**Figure 4.** Figure 4: Regret (%) vs. total solve time (50 instances) at different MIP gap tolerances. [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗

**Figure 5.** Figure 5: Problem-specific graph for CFLP [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗

read the original abstract

Two-Stage Robust Optimization (2RO) with discrete uncertainty is challenging, often rendering exact solutions prohibitive. Scenario reduction alleviates this issue by selecting a small, representative subset of scenarios to enable tractable computation. However, existing methods are largely problem-agnostic, operating solely on the uncertainty set without consulting the feasible region or recourse structure. In this paper, we introduce PRISE, a problem-driven sequential lookahead heuristic that constructs reduced scenario sets by evaluating the marginal impact of each scenario. While PRISE yields high-quality scenario subsets, each selection step requires solving multiple subproblems, making it computationally expensive at scale. To address this, we propose NeurPRISE, a neural surrogate model built on a GNN-Transformer backbone that encodes the per-scenario structure via graph convolution and captures cross-scenario interactions through attention. NeurPRISE is trained via imitation learning with a gain-aware ranking objective, which distills marginal gain information from PRISE into a learned scoring function for scenario ranking and selection. Extensive results on three 2RO problems show that NeurPRISE consistently achieves competitive regret relative to comprehensive methods, maintains strong calability with varying numbers of scenarios, and delivers 7-200x speedup over PRISE. NeurPRISE also exhibits strong zero-shot generalization, effectively handling instances with larger problem scales (up to 5x), more scenarios (up to 4x), and distribution shifts.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

read the letter

NeurPRISE imitates a problem-driven heuristic to cut scenario reduction time in two-stage robust optimization by 7-200x while keeping regret competitive, though the zero-shot generalization claims rest on unverified transfer of marginal rankings. The actual contribution is PRISE, a sequential lookahead method that scores each scenario by its marginal recourse impact after fixing the first-stage solution. That step is problem-aware in a way most reduction techniques are not. NeurPRISE then replaces the repeated subproblem solves with a GNN-Transformer that encodes per-scenario graphs and uses attention across the set, trained by imitation on PRISE's gain ordering. The reported results on three problems show regret close to full-set or exact baselines and clear scaling with scenario count. The zero-shot tests on 5x larger instances and shifted distributions are the part worth watching if they survive full scrutiny. The soft spot is exactly the one the stress-test flags: the surrogate never sees the true recourse costs at inference, so any mismatch between learned ranking and actual marginal costs on new distributions will produce worse subsets than PRISE itself. The abstract gives aggregate speedups and regret numbers, but without the per-instance regret curves, ablation on the attention component, or statistical tests on the generalization cases it is hard to judge how often the approximation holds. The work is aimed at people who already solve 2RO instances in logistics or energy and need something faster than exact reduction or slower heuristics. A reader who cares about practical scalability would get concrete value from the method even if they later replace the surrogate. I would send it to peer review because the core construction is clear, the speedups are large enough to matter, and the experiments are specific enough to be checked.

Referee Report

2 major / 2 minor

Summary. The paper introduces PRISE, a problem-driven sequential lookahead heuristic for scenario reduction in two-stage robust optimization (2RO) with discrete uncertainty that evaluates marginal recourse impacts, and NeurPRISE, a GNN-Transformer neural surrogate trained via imitation learning with a gain-aware ranking objective to approximate PRISE's scoring for fast inference. It claims NeurPRISE delivers competitive regret versus comprehensive methods, 7-200x speedups over PRISE, strong scalability with varying scenario counts, and zero-shot generalization to 5x larger problem scales, 4x more scenarios, and distribution shifts across three 2RO problems.

Significance. If the performance and generalization claims hold after addressing validation gaps, the work would provide a meaningful advance in scalable 2RO by distilling problem-specific heuristic knowledge into a fast neural surrogate, enabling tractable solutions for large uncertainty sets where exact or exhaustive methods are prohibitive.

major comments (2)

[§5] §5 (experimental results): The zero-shot generalization claims (up to 5x scale, 4x scenarios, distribution shifts) rest on the unverified assumption that the GNN-Transformer plus gain-aware ranking preserves the true marginal recourse-cost ordering on shifted instances; without explicit checks comparing surrogate rankings to actual subproblem marginal costs on held-out shifted data, the regret competitiveness cannot be confirmed as load-bearing for the central claim.
[§4] §4 (model and training): The imitation learning setup trains only on PRISE trajectories without recourse-cost correlation verification at inference, so the claim that NeurPRISE approximates marginal impacts without re-solving subproblems is at risk under distribution shifts; this directly affects the reported regret and speedup numbers.

minor comments (2)

[Abstract] Abstract: 'calability' is a typo and should read 'scalability'.
[§5] The experimental section would benefit from explicit definitions of all baselines, number of independent runs, and statistical significance tests to support the regret and speedup tables.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which help clarify the validation needed for our generalization claims. We address each major point below and commit to revisions that directly strengthen the manuscript.

read point-by-point responses

Referee: [§5] §5 (experimental results): The zero-shot generalization claims (up to 5x scale, 4x scenarios, distribution shifts) rest on the unverified assumption that the GNN-Transformer plus gain-aware ranking preserves the true marginal recourse-cost ordering on shifted instances; without explicit checks comparing surrogate rankings to actual subproblem marginal costs on held-out shifted data, the regret competitiveness cannot be confirmed as load-bearing for the central claim.

Authors: We acknowledge that the current manuscript does not include explicit pairwise comparisons of NeurPRISE rankings against true marginal recourse costs on held-out shifted instances. The competitive regret reported on zero-shot instances across scales and shifts provides indirect but consistent evidence that the learned ordering remains effective for scenario selection. To directly address the concern, we will add new experiments in the revised §5 that compute correlation metrics (e.g., Kendall tau) between surrogate scores and exact marginal costs on distribution-shifted test sets. This will confirm the approximation quality and make the regret results load-bearing for the generalization claim. revision: yes
Referee: [§4] §4 (model and training): The imitation learning setup trains only on PRISE trajectories without recourse-cost correlation verification at inference, so the claim that NeurPRISE approximates marginal impacts without re-solving subproblems is at risk under distribution shifts; this directly affects the reported regret and speedup numbers.

Authors: The gain-aware ranking loss is explicitly constructed to distill the relative ordering of marginal gains from PRISE trajectories, enabling inference without repeated subproblem solves. While we do not re-solve at test time (preserving the 7-200x speedup), the end-to-end regret on shifted instances indicates that the approximation remains sufficiently accurate. We agree that explicit correlation verification at inference on shifted data would further substantiate the claim and will incorporate these checks (along with the ranking comparisons noted above) into the revised manuscript. revision: yes

Circularity Check

0 steps flagged

NeurPRISE derivation is self-contained; regret evaluation is independent of imitation training

full rationale

The paper defines PRISE as a lookahead heuristic that computes marginal recourse impacts by repeatedly solving subproblems, then trains NeurPRISE via imitation learning to rank scenarios using a GNN-Transformer that distills those marginal gains. However, all reported performance metrics (regret, scalability, speedup, zero-shot generalization) are obtained by feeding the selected scenario subset into the actual two-stage robust optimization solver on held-out instances and measuring true recourse cost. This external regret computation does not reduce to the imitation objective or training trajectories by construction. No equations or claims in the provided text equate a prediction to its fitted input, invoke load-bearing self-citations for uniqueness, or rename known results. The zero-shot tests on larger scales and shifted distributions further rely on independent optimization benchmarks rather than internal consistency checks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The approach rests on standard assumptions from robust optimization (worst-case recourse) and supervised imitation learning; no new free parameters, axioms, or invented entities are introduced beyond the neural architecture itself.

pith-pipeline@v0.9.0 · 5567 in / 1283 out tokens · 51021 ms · 2026-05-15T02:00:16.509140+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 1 internal anchor

[1]

Robust solutions of linear programming problems contaminated with uncertain data.Mathematical programming, 88(3):411–424, 2000

Aharon Ben-Tal and Arkadi Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data.Mathematical programming, 88(3):411–424, 2000

work page 2000
[2]

Adjustable robust solutions of uncertain linear programs.Mathematical programming, 99(2):351–376, 2004

Aharon Ben-Tal, Alexander Goryashko, Elana Guslitzer, and Arkadi Nemirovski. Adjustable robust solutions of uncertain linear programs.Mathematical programming, 99(2):351–376, 2004

work page 2004
[3]

Princeton University Press, 2009

Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.Robust Optimization. Princeton University Press, 2009

work page 2009
[4]

Finite adaptability in multistage linear optimization.IEEE Transactions on Automatic Control, 55(12):2751–2766, 2010

Dimitris Bertsimas and Constantine Caramanis. Finite adaptability in multistage linear optimization.IEEE Transactions on Automatic Control, 55(12):2751–2766, 2010

work page 2010
[5]

Design of near optimal decision rules in multistage adaptive mixed-integer optimization.Operations Research, 63(3):610–627, 2015

Dimitris Bertsimas and Angelos Georghiou. Design of near optimal decision rules in multistage adaptive mixed-integer optimization.Operations Research, 63(3):610–627, 2015

work page 2015
[6]

Binary decision rules for multistage adaptive mixed-integer optimization.Mathematical Programming, 167(2):395–433, 2018

Dimitris Bertsimas and Angelos Georghiou. Binary decision rules for multistage adaptive mixed-integer optimization.Mathematical Programming, 167(2):395–433, 2018

work page 2018
[7]

A machine learning approach to two-stage adaptive robust optimization.European Journal of Operational Research, 319(1):16–30, 2024

Dimitris Bertsimas and Cheol Woo Kim. A machine learning approach to two-stage adaptive robust optimization.European Journal of Operational Research, 319(1):16–30, 2024

work page 2024
[8]

Optimization-based scenario reduction for data-driven two-stage stochastic optimization.Operations Research, 71(4):1343–1361, 2023

Dimitris Bertsimas and Nishanth Mundru. Optimization-based scenario reduction for data-driven two-stage stochastic optimization.Operations Research, 71(4):1343–1361, 2023

work page 2023
[9]

The price of robustness.Operations research, 52(1):35–53, 2004

Dimitris Bertsimas and Melvyn Sim. The price of robustness.Operations research, 52(1):35–53, 2004

work page 2004
[10]

Robust and data-driven optimization: modern decision making under uncertainty

Dimitris Bertsimas and Aurélie Thiele. Robust and data-driven optimization: modern decision making under uncertainty. InModels, methods, and applications for innovative decision making, pages 95–122. INFORMS, 2006

work page 2006
[11]

A deep generative learning approach for two-stage adaptive robust optimization

Aron Brenner, Rahman Khorramfar, Jennifer Z Sun, and Saurabh Amin. A deep generative learning approach for two-stage adaptive robust optimization. InThe Thirteenth International Conference on Learning Representations, 2025. URLhttps://openreview.net/forum?id=CKXul9iX77

work page 2025
[12]

Neur2RO: Neural two-stage robust optimization

Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias Boutros Khalil. Neur2RO: Neural two-stage robust optimization. InThe Twelfth International Conference on Learning Representations, 2024

work page 2024
[13]

Scenario reduction in stochastic programming

Jitka Dupaˇcová, Nicole Gröwe-Kuska, and Werner Römisch. Scenario reduction in stochastic programming. Mathematical programming, 95(3):493–511, 2003

work page 2003
[14]

Problem-driven scenario reduction and scenario approximation for robust optimization.arXiv preprint arXiv:2410.08863, 2024

Jamie Fairbrother, Marc Goerigk, and Mohammad Khosravi. Problem-driven scenario reduction and scenario approximation for robust optimization.arXiv preprint arXiv:2410.08863, 2024

work page arXiv 2024
[15]

Fast Graph Representation Learning with PyTorch Geometric

Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with PyTorch Geometric. InICLR Workshop on Representation Learning on Graphs and Manifolds, 2019. URL https://arxiv.org/ abs/1903.02428. arXiv:1903.02428

work page internal anchor Pith review Pith/arXiv arXiv 2019
[16]

Exact combinatorial optimization with graph convolutional neural networks.Advances in neural information processing systems, 32, 2019

Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks.Advances in neural information processing systems, 32, 2019

work page 2019
[17]

Representative scenario construction and preprocessing for robust combinatorial optimization problems.Optimization Letters, 13(6):1417–1431, 2019

Marc Goerigk and Martin Hughes. Representative scenario construction and preprocessing for robust combinatorial optimization problems.Optimization Letters, 13(6):1417–1431, 2019

work page 2019
[18]

Optimal scenario reduction for one-and two-stage robust optimization with discrete uncertainty in the objective.European Journal of Operational Research, 310(2): 529–551, 2023

Marc Goerigk and Mohammad Khosravi. Optimal scenario reduction for one-and two-stage robust optimization with discrete uncertainty in the objective.European Journal of Operational Research, 310(2): 529–551, 2023. 10

work page 2023
[19]

Data-driven prediction of relevant scenarios for robust combinatorial optimization.Computers & Operations Research, 174:106886, 2025

Marc Goerigk and Jannis Kurtz. Data-driven prediction of relevant scenarios for robust combinatorial optimization.Computers & Operations Research, 174:106886, 2025

work page 2025
[20]

URL https://docs.gurobi

Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual, 2025. URL https://docs.gurobi. com/projects/optimizer/en/12.0/. Version 12.0.0

work page 2025
[21]

K-adaptability in two-stage robust binary programming.Operations Research, 63(4):877–891, 2015

Grani A Hanasusanto, Daniel Kuhn, and Wolfram Wiesemann. K-adaptability in two-stage robust binary programming.Operations Research, 63(4):877–891, 2015

work page 2015
[22]

Scenario reduction algorithms in stochastic programming.Computa- tional optimization and applications, 24(2):187–206, 2003

Holger Heitsch and Werner Römisch. Scenario reduction algorithms in stochastic programming.Computa- tional optimization and applications, 24(2):187–206, 2003

work page 2003
[23]

Problem-based optimal scenario generation and reduction in stochastic programming.Mathematical Programming, 191(1):183–205, 2022

Réne Henrion and Werner Römisch. Problem-based optimal scenario generation and reduction in stochastic programming.Mathematical Programming, 191(1):183–205, 2022

work page 2022
[24]

Decision-based scenario clustering for decision-making under uncertainty.Annals of Operations Research, 315(2):747–771, 2022

Mike Hewitt, Janosch Ortmann, and Walter Rei. Decision-based scenario clustering for decision-making under uncertainty.Annals of Operations Research, 315(2):747–771, 2022

work page 2022
[25]

Strategies for pre-training graph neural networks

Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. InInternational Conference on Learning Representations, 2020

work page 2020
[26]

Robust discrete optimization under discrete and interval uncertainty: A survey

Adam Kasperski and Paweł Zieli´nski. Robust discrete optimization under discrete and interval uncertainty: A survey. InRobustness analysis in decision aiding, optimization, and analytics, pages 113–143. Springer, 2016

work page 2016
[27]

Problem-driven scenario clustering in stochastic optimization.Computational Management Science, 20(1):13, 2023

Julien Keutchayan, Janosch Ortmann, and Walter Rei. Problem-driven scenario clustering in stochastic optimization.Computational Management Science, 20(1):13, 2023

work page 2023
[28]

PyTorch: An imperative style, high-performance deep learning library.Advances in neural information processing systems, 32, 2019

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An imperative style, high-performance deep learning library.Advances in neural information processing systems, 32, 2019

work page 2019
[29]

Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set.INFORMS Journal on Computing, 28(3):553–574, 2016

Krzysztof Postek and Dick den Hertog. Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set.INFORMS Journal on Computing, 28(3):553–574, 2016

work page 2016
[30]

Allen L. Soyster. Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming.Operations Research, 21(5):1154–1157, 1973

work page 1973
[31]

K-adaptability in two-stage mixed-integer robust optimization.Mathematical Programming Computation, 12(2):193–224, 2020

Anirudh Subramanyam, Chrysanthos E Gounaris, and Wolfram Wiesemann. K-adaptability in two-stage mixed-integer robust optimization.Mathematical Programming Computation, 12(2):193–224, 2020

work page 2020
[32]

HGCN2SP: Hierarchical graph convolutional network for two-stage stochastic programming

Yang Wu, Yifan Zhang, Zhenxing Liang, and Jian Cheng. HGCN2SP: Hierarchical graph convolutional network for two-stage stochastic programming. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of the 41st International Conference on Machine Learning, volume 235 ...

work page 2024
[33]

Learning scenario representation for solving two-stage stochastic integer programs

Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning scenario representation for solving two-stage stochastic integer programs. InInternational Conference on Learning Representations, 2022

work page 2022
[34]

How powerful are graph neural networks? InInternational Conference on Learning Representations, 2019

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? InInternational Conference on Learning Representations, 2019. URL https://openreview.net/ forum?id=ryGs6iA5Km

work page 2019
[35]

Solving two-stage robust optimization problems using a column-and-constraint generation method.Operations Research Letters, 41(5):457–461, 2013

Bo Zeng and Long Zhao. Solving two-stage robust optimization problems using a column-and-constraint generation method.Operations Research Letters, 41(5):457–461, 2013

work page 2013
[36]

which scenario is worst for the current solution?

Long Zhao and Bo Zeng. An exact algorithm for two-stage robust optimization with mixed integer recourse problems, 2012. 11 Appendix Contents A Notation 13 B PRISE: Method Details 13 B.1 Monotonicity of the reduced-scenario objective value . . . . . . . . . . . . . . . . 13 B.2 PRISE Compression Budget and Convergence Comparison . . . . . . . . . . . . . 1...

work page 2012
[37]

configurations: min x, z, η,{y (s)} Pm j=1 fj xj +Pm j=1 aj zj +η s.t.η≥ Pn i=1 Pm j=1 cij y(s) ij ,∀s∈[S], zj ≤K j xj,∀j∈[m], Pn i=1 y(s) ij ≤z j,∀j∈[m],∀s∈[S], Pm j=1 y(s) ij ≥d (s) i ,∀i∈[n],∀s∈[S], y(s) ij ≥0, z j ≥0, x j ∈ {0,1}. (21) Note that the scenario-dependent term d(s) i appears in the demand constraint RHS (line 3), not in the objective coef...

work page