Research map / Learning theory and algorithms / Prediction and decision losses

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

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Distributionally robust optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes PRISE, a problem-driven sequential lookahead heuristic for scenario reduction in two-stage robust optimization, and NeurPRISE, a GNN-Transformer surrogate trained by imitation with a score-weighted KL loss to replicate PRISE's selection at a fraction of the cost.

Problem

Two-stage robust optimization with discrete uncertainty is computationally hard; existing scenario reduction methods ignore the feasible region and recourse structure, and the problem-driven alternative (PRISE) is too expensive because each step solves many MILPs.

Approach

Scenario reduction framed as greedy marginal-gain selection on the reduced robust objective (problem-driven), with a learned GNN-Transformer scorer trained via imitation of those marginal gains using a soft-target KL loss, enabling one-pass top-k selection.

Key results

• On small SEL instances at k=6, NeurPRISE reaches 0.42% regret versus 0.82% for PRISE and 1.96% for MaxSum, with about 5.9 s vs 132 s for PRISE.
• On VC small instances at k=6, NeurPRISE achieves 2.34% regret versus 4.40% for MaxSum and 1.04% for PRISE, at 53.9 s vs 5,680 s for PRISE.
• NeurPRISE generalizes zero-shot to 5x problem size, giving lowest SEL regret across all budgets (e.g., 0.81% vs 2.96% for MaxSum at k=6).

Surprising findings

• Neur2RO attains the lowest regret at k=1 on VC medium and large instances, beating NeurPRISE.
• PRISE is not submodular in general, though empirical gains are non-increasing in 93-99% of instances.

Limitations

• PRISE labeling is expensive (about 14.5 wall-clock hours for small-scale training labels), and labeling cost grows at larger scales.
• Only two problem classes are fully reported in main text (SEL, VC); CFLP deferred to appendix.
• Neur2RO outperforms NeurPRISE at k=1 on VC in several settings.

Experimental setup

Datasets: synthetic SEL instances (uniform costs) synthetic VC instances (random graphs)

Benchmarks: Selection (SEL) Vertex Cover (VC)

Metrics: regret (%) wall-clock time (s)

Baselines: Exact (Gurobi) Random K-means MaxSum SOR Neur2RO

Builds on: Neur2RO column-and-constraint generation GINE

Closest papers by meaning

• HGCN2SP: Hierarchical Graph Convolutional Network for Two-Stage Stochastic Programming (ICML 2024 · similarity 0.86)
• A Deep Generative Learning Approach for Two-stage Adaptive Robust Optimization (ICLR 2025 · similarity 0.85)
• Automated Reformulation of Robust Optimization via Memory-Augmented Large Language Models (NeurIPS 2026 · similarity 0.84)
• Towards Robust Learning to Optimize with Theoretical Guarantees (CVPR 2024 · similarity 0.83)
• Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach (ICML 2025 · similarity 0.83)
• Distributionally Robust Optimization with Bias and Variance Reduction (ICLR 2024 · similarity 0.83)