불확실성이 이산적인 이단계 강건 최적화 문제에서의 시나리오 축소 기법

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

불확실성이 이산적인 이단계 강건 최적화(2RO) 문제는 해결하기 어렵고, 종종 정확한 해를 구하는 데 엄청난 계산 비용이 소요됩니다. 시나리오 축소 기법은 계산 가능성을 높이기 위해, 전체 시나리오 집합에서 작고 대표적인 부분 집합을 선택하는 방식으로 이 문제를 완화합니다. 그러나 기존 방법들은 대부분 문제에 특화되지 않으며, 불확실성 집합만을 사용하여 실행되고, 실행 가능 영역이나 대응 구조를 고려하지 않습니다. 본 논문에서는 문제 중심의 순차적 탐색 휴리스틱인 PRISE를 소개합니다. PRISE는 각 시나리오의 주변 영향력을 평가하여 축소된 시나리오 집합을 구성합니다. PRISE는 고품질의 시나리오 부분 집합을 제공하지만, 각 선택 단계마다 여러 개의 하위 문제를 해결해야 하므로, 규모가 커질수록 계산 비용이 높아집니다. 이러한 문제를 해결하기 위해, 본 논문에서는 그래프 컨볼루션(graph convolution)을 통해 각 시나리오의 구조를 인코딩하고, 어텐션(attention)을 통해 시나리오 간의 상호 작용을 파악하는 GNN-Transformer 기반의 신경망 서브 모델인 NeurPRISE를 제안합니다. NeurPRISE는 이익을 고려한 순위 기반 학습을 통해 훈련되며, PRISE에서 얻은 주변 이익 정보를 학습된 평가 함수로 추출하여 시나리오의 순위 결정 및 선택에 활용합니다. 세 가지 2RO 문제에 대한 광범위한 실험 결과는 NeurPRISE가 종합적인 방법과 비교하여 경쟁력 있는 후회를 달성하고, 다양한 시나리오 개수에 대해 강력한 확장성을 유지하며, PRISE보다 7배에서 200배 빠른 속도를 제공한다는 것을 보여줍니다. 또한, NeurPRISE는 뛰어난 제로샷 일반화 능력을 보여주며, 더 큰 규모의 문제(최대 5배), 더 많은 시나리오(최대 4배), 그리고 데이터 분포 변화에 효과적으로 대응합니다.

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.