通过基于物理知识的图学习方法解决大规模机组调度问题

《IEEE Transactions on Power Systems》：Solve Large-Scale Unit Commitment Problems by Physics-Informed Graph Learning

　　单位 commitment问题通过引入图神经网络优化分支与边界算法，提出PI-GCN用于神经潜水和MB-GCN用于神经分支，构建新型神经MIP求解器，显著提升大规模问题的计算效率与解的质量。

　　

摘要：

单元承诺（Unit Commitment, UC）问题通常被构建为混合整数程序（Mixed-Integer Program, MIP），并通过分支定界（Branch-and-Bound, B&B）算法求解。图神经网络（Graph Neural Networks, GNN）的最新进展使得GNN能够通过学习“下沉”和“分支”的策略来提升现代MIP求解器的性能。现有的用于解决MIP问题的GNN模型大多基于数学公式构建，在处理大规模UC问题时计算成本较高。在本文中，我们提出了一种基于物理特性的分层图卷积网络（Physics-Informed Hierarchical Graph Convolutional Network, PI-GCN），该网络利用电力系统各组件的内在特征来寻找高质量的变量分配方案。此外，我们还采用了基于MIP模型的图卷积网络（MIP-Based Graph Convolutional Network, MB-GCN）来实现“神经分支”功能，以在B&B树的每个节点选择最优的分支变量。最后，我们将“神经下沉”和“神经分支”集成到现代MIP求解器中，构建了一种专为大规模UC问题设计的新颖神经MIP求解器。数值研究表明，与基线MB-GCN相比，PI-GCN在“神经下沉”方面的性能和可扩展性更优。而且，结合我们提出的神经下沉模型和基线神经分支模型后，这种神经MIP求解器在所有测试日的运行成本最低，并且性能优于传统的现代MIP求解器。

引言

单元承诺（UC）是日前电力市场中的一个基本优化问题。在给定供应报价、需求出价和输电系统条件的情况下，独立系统运营商（Independent System Operator, ISO）需要在有限的时间内确定发电机组的最佳运行计划。UC问题通常被构建为混合整数程序（MIP），并通过数学优化算法进行求解，这些算法包括分支割（Branch-and-Cut, B&C）[1]、拉格朗日松弛（Lagrangian Relaxation, LR）[2][3]、Benders分解（Benders Decomposition）[4][5]、外部近似（Outer Approximation）[6]、序数优化（Ordinal Optimization）[7]以及列生成与约束生成（Column and Constraint Generation）[8]等。其中，B&C方法将分支定界（B&B）算法与割平面（Cutting Planes）相结合，有效提高了算法的效率，已被广泛应用于Gurobi [9]、CPLEX [10]、SCIP [11]和Xpress [12]等现代求解器中。对于大规模UC问题[13]，B&B树的规模可能非常大，从而导致计算时间显著增加。