用分层图网络优化随机规划的场景选择,提速且泛化强。
HGCN2SP: Hierarchical Graph Convolutional Network for Two-Stage Stochastic Programming
- 构建分层图网络编码场景关系,按最优顺序选择
- 在经典问题上实现高质量解,计算时间显著缩短
- 对未见规模问题有强泛化能力,适合大规模场景
两阶段随机规划(2SP)是建模不确定性下决策问题的标准框架。尽管已有多种方法,但面对大量情景时求解仍具挑战性。当前方案多依赖聚类或蒙特卡洛采样,未能深度整合情景信息,且忽略情景顺序对求解时间的重要影响。为此,我们提出HGCN2SP,一种面向2SP问题的新型分层图神经网络模型,通过分层图结构编码每个情景并建模其关系。模型采用强化学习训练,利用求解器反馈优化策略;策略网络结合分层图卷积网络进行特征提取,以及基于注意力的解码器实现有序情景选择。在两个经典2SP问题上的实验表明,HGCN2SP能在极短时间内生成高质量决策。此外,该模型在处理大规模实例时表现出卓越泛化能力,即使变量或情景数量远超训练阶段所见,仍能有效运行。
原文摘要 · Abstract (English)
Two-stage Stochastic Programming (2SP) is a standard framework for modeling decision-making problems under uncertainty. While numerous methods exist, solving such problems with many scenarios remains challenging. Selecting representative scenarios is a practical method for accelerating solutions. However, current approaches typically rely on clustering or Monte Carlo sampling, failing to integrate scenario information deeply and overlooking the significant impact of the scenario order on solving time. To address these issues, we develop HGCN2SP, a novel model with a hierarchical graph designed for 2SP problems, encoding each scenario and modeling their relationships hierarchically. The model is trained in a reinforcement learning paradigm to utilize the feedback of the solver. The policy network is equipped with a hierarchical graph convolutional network for feature encoding and an attention-based decoder for scenario selection in proper order. Evaluation of two classic 2SP problems demonstrates that HGCN2SP provides high-quality decisions in a short computational time. Furthermore, HGCN2SP exhibits remarkable generalization capabilities in handling large-scale instances, even with a substantial number of variables or scenarios that were unseen during the training phase.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。