高效求解大规模机组组合的两阶段列生成算法

来源：计算数学杂志2026年第1期北京时间：

作者：苏昭纲, 汤宇杨, 陈圣杰, 陈亮, 邓家懿

单位：中国科学院数学与系统科学研究院, 计算数学与科学工程计算研究所, 北京 100190

摘要：机组组合问题(Unit Commitment Problem,UC)是电力系统运行优化的核心难题,随着电力系统规模的急剧扩大,混合整数规划(Mixed Integer Programming,MIP)方法面临着严峻的计算挑战.本文创新性提出一种两阶段列生成算法来高效求解大规模机组组合问题.该方法基于Dantzig-Wolfe分解理论,通过引入调度策略变量将原问题重构,实现了机组间的有效解耦.我们针对该重构模型提出了两阶段计算方法:第一阶段采用并行列生成方法求解线性规划(Linear Programming,LP)松弛问题;第二阶段在生成列的基础上求解限制主问题得到高质量的整数可行解.在包含1000至1500台机组的大规模机组组合测试实例上进行的数值实验表明,所提方法相比商业求解器CPLEX在求解时间上平均实现了2.5倍以上的加速,最优值相对误差控制在0.01%左右,且求解时间十分稳定,具备良好的可扩展性.该算法为大规模电力系统的实际调度优化提供了有效的计算工具,具有重要的理论意义和实用价值.

关键词：机组组合,列生成,Dantzig-Wolfe分解,混合整数规划,电力系统优化

基金资助：重点研发计划(2022YFB2403400)资助.