arXiv:2605.14494cs.AIcs.LG2026-05

用神经网络加速鲁棒优化中的场景缩减,速度快7-200倍。

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

论文配图:Learning Scenario Reduction for Two-Stage Robust Optimization with Discrete Uncertainty
图 1 · 摘自论文原文
  • 基于问题结构的渐进式选择方法,评估每种场景的边际影响。
  • 在三种2阶段鲁棒优化任务中,性能接近最优,且可扩展性更强。
  • 支持零样本泛化,适用于更大规模或分布变化的问题。

离散不确定性下的两阶段鲁棒优化(2RO)求解困难,精确解常不可行。场景缩减通过选取少量代表性场景来降低计算复杂度。然而现有方法多为通用策略,仅依赖不确定性集而忽略可行域与后续调整结构。本文提出PRISE,一种基于问题驱动的逐次前瞻启发式算法,通过评估每个场景的边际影响构建精简场景集。尽管效果优异,但每次选择需求解多个子问题,计算开销大。为此,我们提出NeurPRISE,一个基于GNN-Transformer架构的神经代理模型,利用图卷积编码单个场景结构,通过注意力机制捕捉跨场景关联。该模型通过模仿学习与增益感知排序目标训练,从PRISE中提取场景增益信息,生成可推广的评分函数用于场景排序与选择。在三个2RO问题上的大量实验表明,NeurPRISE在保持与全面方法相当的遗憾水平的同时,具备强可扩展性,且相较PRISE提速7至200倍。此外,其零样本泛化能力出色,能有效应对规模扩大5倍、场景数增加4倍及分布偏移的情况。

原文摘要 · Abstract (English)

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.

鲁棒优化场景缩减神经网络加速计算

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。