机组组合问题的不可行割平面法：加速MIP求解的新途径

《CSEE Journal of Power and Energy Systems》：Infeasibility Cutting Plane for Unit Commitment Problem

本刊编辑推荐：针对机组组合(UC)这一NP难问题，研究团队创新性提出"不可行割平面"方法。该方法通过构造排除导致UC不可行的整数变量组合的逻辑约束，在不影响可行解的同时收紧线性规划松弛(LP relaxation)，实现了1.14-2.41倍的求解加速。研究建立了有效割平面的理论判据，并设计了高效的并行生成框架，在30个测试案例中验证了其有效性，为电力系统优化提供了新思路。

　　

在现代电力系统中，机组组合(Unit Commitment, UC)问题扮演着至关重要的角色。作为电力市场出清和短期发电计划的核心，UC问题的求解质量直接关系到电网的安全经济运行。然而，这一典型的组合优化问题被证明是NP难问题，即使采用最先进的商业求解器，在面对大规模整数变量和紧张约束条件时，仍然面临计算挑战。

目前，电力系统运营商在实际应用中往往需要接受非零的MIP间隙(MIP-gap)，这意味着无法保证获得最优解。考虑到每天调度电量的巨大规模，非最优解可能导致显著的经济损失。现有研究主要从两个方向寻求突破：一是通过聚类或预固定整数变量来减少模型规模，二是改进分支定界(Branch-and-Bound, B&B)算法过程。然而，这些方法在保证通用UC案例最优性方面存在困难，因为很难在优化前精确确定"无用"的整数变量或约束。

正是在这一背景下，重庆大学的研究团队在《CSEE Journal of Power and Energy Systems》上发表了创新性研究成果，提出了一种专门针对UC问题的不可行割平面(Infeasibility Cutting Plane)方法。该方法巧妙地将电力系统领域知识与通用数学技术相结合，为UC问题求解提供了新的加速途径。

研究团队采用的核心技术方法包括：基于连续UC模型构造不可行解、通过阈值舍入策略生成不可行固定集、利用目标函数扰动避免割平面重叠、基于LP热启动的加速技术，以及通过理论判据验证割平面有效性。这些方法共同构成了一个高效的不可行割平面生成框架。

不可行割平面的构建与理论验证

研究团队首先将UC问题中的整数变量分为三类：自由变量(z_opt)、固定为1的变量(z_fix^on)和固定为0的变量(z_fix^off)。特别关注那些会导致UC问题不可行的固定集，记为zˉfix={zˉfixon,zˉfixoff}。

基于这些不可行固定集，研究构建了不可行割平面的数学表达式：

g(xˉ)=Ug,t∈zˉfixon∑(1?Ug,t)+Ug,t∈zˉfixoff∑Ug,t≥1

这一逻辑约束确保了至少有一个整数变量不采用导致不可行的取值。理论研究证明，该割平面满足有效割平面的两个关键特征：一是不影响UC问题的任何可行解，二是能够收紧UC的LP松弛。

为了直观说明不可行割平面的存在性，研究团队提供了一个简单的两机组示例。该系统存在两个不可行整数变量组合：(U₁, U₂) = (0,0)和(1,0)，分别对应两台机组都停运和仅G₁运行的情况。基于这些不可行组合构建的割平面U₁+ U₂≥ 1和-U₁+ U₂≥ 0，有效排除了不可行解同时收紧了解空间。

高效生成不可行割平面的框架

研究团队提出了一套系统化的不可行割平面生成框架，该框架的核心是通过求解一系列连续UC模型来快速获得多个不可行解。

连续UC模型通过两个关键修改构建：一是所有机组在调度期间设置为启动状态，二是所有机组的最小输出限制设置为0。该模型的数学表述为：

目标函数：min∑t∈T∑g∈GCgPg,t

约束条件包括松弛后的输出限制和爬坡约束，以及功率平衡、支路潮流和N-1安全约束。

通过求解这一LP问题获得解x_c^*后，采用阈值舍入策略将分数值的整数变量固定为0或1：

Ug,t={1,0,min{Pg,t?∣?t∈T}≥δonPg,minmax{Pg,t?∣?t∈T}≤δoffPg,min

当阈值设置较为激进时，舍入后的整数组合很可能导致UC问题不可行，从而生成不可行固定集zˉfix。

为了高效生成多样化的割平面，研究团队采用了并行计算框架，通过扰动目标函数获得不同的最优解，避免生成重叠的割平面。具体而言，当扰动系数α满足α_Bη₁> α(c_cⁱ)^T时，可以确保扰动后的LP问题具有不同的最优解。

此外，研究还采用了LP热启动技术来加速连续模型的求解过程，将前一个连续模型的最优解作为后一个模型的初始解，显著减少了计算时间。

案例验证与性能分析

研究团队在30个公开和实际系统案例上验证了所提方法的有效性，包括RTS-GMLC、IEEE-118和中国某实际电力系统案例。测试结果表明，不可行割平面方法在不同规模的UC问题上均表现出良好的加速效果。

在有效性方面，生成的不可行割平面中，满足有效性判据的比例在不同测试集上分别达到76.4%、100%和66.9%，表明所提框架能够有效生成可收紧LP松弛且对可行解无影响的割平面。

在计算效率方面，与直接使用GUROBI求解器相比，加入不可行割平面后实现了1.14-2.41倍的加速。即使考虑割平面生成时间，整体加速比仍达到1.13-2.17倍，且完全保证最优性。

收敛过程分析显示，加入不可行割平面后，MIP间隙的收敛速度明显加快，表明割平面有效收紧了解空间，提高了B&B算法的搜索效率。

研究团队还深入分析了割平面数量与加速效益之间的权衡关系。定义效益指标η = (T_o- T_c)/T_g，其中T_o为原始求解时间，T_c为加速后求解时间，T_g为割平面生成时间。当η > 1时，表明割平面生成的时间成本小于其带来的加速效益。实验结果显示，在割平面数量为10-1000范围内，几乎所有割平面都产生了加速效益，且当数量为100时达到最大效益。

与现有割平面技术的兼容性

现代MIP求解器(如GUROBI)已集成了多种通用割平面生成器，包括Gomory混合整数割、混合整数舍入不等式、{0,1/2}-Chvátal-Gomory割等。为了验证所提方法与现有割平面技术的兼容性，研究团队在不同割平面强度设置下进行了对比实验。

结果表明，不可行割平面在各种设置下均能实现加速，证明其与现有割平面技术具有良好的兼容性。当求解器内置割平面生成较为激进时，不可行割平面的相对效果会有所减弱，这主要是因为LP松弛已经被现有割平面充分收紧，同时激进的割平面生成增加了计算负担。

研究结论与意义

本研究提出的不可行割平面方法，通过将电力系统领域知识与数学优化理论相结合，为UC问题求解提供了有效的加速途径。理论分析证明了不可行割平面在收紧LP松弛方面的有效性，而实用化生成框架则确保了方法的高效性。

该研究的主要贡献包括：首次系统提出了针对UC问题的不可行割平面概念并建立了理论验证框架；设计了高效的并行生成算法，能够快速获得多个高质量的割平面；通过大量案例验证了方法的实用性和有效性。

不可行割平面方法的成功，展示了将领域知识嵌入通用数学优化框架的潜力。这一思路可进一步扩展至考虑不确定性的UC问题，其中领域特定的方法或启发式技术可用于提取接近最优UC解的信息，从而指导算法更快收敛。

对于电力系统实际应用而言，该方法提供了一种保证最优性的加速技术，有助于系统运营商在复杂运行条件下快速获得高质量调度方案，提升电网运行的经济性和安全性。随着电力系统规模的不断扩大和运行环境的日益复杂，这种基于领域知识的优化加速技术将发挥越来越重要的作用。