（1）
摘要 随着电力现货市场交易范围的不断扩大，通用混合整数规划求解器求解大规模安全约束机组组合模型越发困难。本着破解商用求解器“卡脖子”难题的初衷，该文提出一种混合分支方法定制开源HiGHS求解器的分支策略。该方法由变量选择规则及规则切换策略组成，变量选择规则利用机组组合物理模型中0-1变量类型、机组容量、时段顺序和费用等方面特点；规则切换策略则针对分支过程间隙下降瓶颈问题确定了容量混合规则与平均费用规则的切换条件。此外，还根据0-1变量类型对应用强分支的策略进行了定制。IEEE 118节点系统、RTE 1888节点系统及Polish 2383节点系统的仿真结果表明，所提混合分支方法能产生较小搜索树，使开源HiGHS求解器求解安全约束机组组合问题的速度提升46%～62%。所提定制化方法为我国开发自主可控的安全约束机组组合求解器提供了新的思路。
关键词：安全约束机组组合 混合整数线性规划 求解器 分支方法 开源
随着我国电力市场建设稳步有序推进，多元竞争主体格局初步形成[1]，市场化交易电量比重大幅提升。安全约束机组组合（Security Constrained Unit Commitment, SCUC）是电力现货市场中重要的优化问题之一，通常建模为混合整数线性规划（Mixed Integer Linear Programming, MILP）模型，并直接调用通用MILP求解器求解。虽然通用MILP求解器的性能在最近十几年随着计算机硬件技术及分支割平面（Branch and Cut, B&C）算法理论的发展得到极大的提升，但随着电力现货市场范围的扩大及交易主体数量的增加，实际中求解器求解SCUC问题依然面临着收敛缓慢或难以收敛的瓶颈[2-3]。
大量安全约束和0-1变量使SCUC的MILP模型全局最优解的寻找变得尤为困难[4]。为了提高SCUC问题的求解速度，研究人员在MILP模型处理与求解算法两方面进行了诸多研究。在模型处理方面，多为辨识冗余约束或越限约束，并对模型中的约束进行削减，构造更为简洁和紧凑的SCUC模型，从而减小SCUC模型的规模[5-7]。在算法方面，文献[8]基于现货市场出清过程中的机组收益，迭代求解通过固定具有最优收益机组的部分0-1变量并将冗余安全约束设置为惰性约束得到的小规模子问题来快速获取原问题的最优解。文献[9]利用松弛解的趋向性提出了一种包含基于松弛邻域搜索（Relaxation-based Neighborhood Search, RNS）和改进松弛诱导（Improved Relaxation Inducement, IRI）的算法，在原问题的基础上生成并添加RNS约束和诱导函数形成子问题，子问题的可行解用于原问题热启动。文献[10]通过构建并求解时段诱导子问题，借助求解器的割平面生成功能获取并转换诱导割平面。
我国电力现货市场中的SCUC问题求解目前主要依赖美国的Gurobi和CPLEX等商用求解器。这些商用求解器受出口管制的风险很大，是我国现货市场的“卡脖子”问题。在我国电力市场化改革持续推进的背景下，电力现货市场对具有自主知识产权的高效求解器的需求日益凸显[11]。近年来随着开源理念的传播，B&C 算法的开源项目受到越来越多的关注，虽然它与商用求解器在性能上还有较大差距，但它为我国开发自主可控的SCUC求解器提供了很好的定制化平台。
为此，文献[12]深入CBC开源求解器内部，根据UC问题的物理特点提出了一种基于B&C算法框架的定制化固定-推断（Fix and Implicate, F&I）启发式方法，提高了求解器的求解效率。但是所提方法求解的模型没有涉及安全约束，CBC开源求解器的可维护性较差，定制化的思路还有待与求解器更多求解过程结合。文献[13]利用SCUC问题的参数和特性提出了两种启发式方法，有选择地固定0-1变量，提高了SCUC问题的计算速度。虽然这两种启发式方法在CBC开源求解器上实现，但它们可以嵌入其他MILP求解器中。文献[14]则基于分析中心理论，结合SCUC模型特点对开源HiGHS求解器内部的启发式方法进行深度定制，提高了HiGHS求解器求解SCUC问题的效率。
在电力现货市场中，SCUC问题以“模型建立和处理+求解器”的模式求解，虽然研究人员在MILP求解器的外部模型优化即模型建立和处理方面提出了许多加速求解方法，但都是将求解器当作黑盒。实际上，求解器算法内部完全可以结合SCUC物理模型的信息，从而获得进一步的性能提升。
现代MILP求解器内部由许多加速策略组成，如分支策略、启发式策略和节点选择策略等。这些策略相互耦合，从不同的角度共同影响B&C算法的求解过程和效率。其中分支策略是B&C算法的核心，决定了整个分支定界树的结构和形状，其他策略都建立在分支所产生的搜索树之上。因此对B&C算法中的分支策略进行定制是从MILP求解器的内部入手进行定制化需优先考量的方向。
鉴于MILP商业求解器的黑盒特性，本文基于当前最快的开源求解器——HiGHS[15]，从求解器算法的内部入手，结合机组的物理特性及SCUC问题的时序等特点，提出一种基于机组参数的混合分支（Unit Parameter-based Hybrid Branching, UPHB）方法以替代HiGHS默认的分支方法。该混合分支策略只选择机组的开停机状态变量作为候选分支变量，由变量选择规则及其切换策略组成。变量选择规则利用机组组合物理模型中0-1变量类型、机组容量、时段顺序和费用等方面特点；规则切换策略则针对分支过程中的间隙下降瓶颈问题，确定了容量混合规则与平均费用规则的切换条件，并在适当的时机切换变量选择规则，以改变搜索方向。最后在选择了分支变量后，根据分支变量的可靠性仅对机组开停状态0-1变量应用强分支策略。IEEE 118节点系统、RTE 1888节点系统及Polish 2383系统的仿真结果表明，该混合分支方法能够大幅提升利用B&C算法求解SCUC问题的速度。
SCUC 是指在电力现货市场出清过程中，制定满足电力系统安全性约束条件、能使社会福利最大化的机组开停机计划。本文使用四类0-1变量的SCUC的MILP模型[16]，包括社会福利最大化的目标函数、系统功率平衡约束、机组爬坡约束、机组最小起停时间约束和线路安全约束等约束。
1）目标函数
电力现货市场出清中SCUC以社会福利最大为优化目标，包括机组的运行费用、起动费用和最小技术出力费用，即
（1）
式中，
、
和
分别为机组
在时段
的运行费用、起动费用和最小技术出力费用；
为机组在时段的有功出力；
为时段总数；
为机组总数。机组运行费用是与机组申报的各段出力区间和对应能量价格有关的分段线性函数，具体可表示为
（2）
式中，
为机组报价总段数；
为机组申报的第
个出力区间对应的能量价格；
为机组在时段第个出力区间的中标出力。
机组起动费用
是与机组起动状态有关的函数，表示机组在不同状态（冷态/热态）下的起动费用，可表示为
（3）
式中，
为机组起动状态0-1变量，=1表示机组在时段执行起动操作；
为机组冷起动状态0-1变量，=1表示机组在时段执行冷起动操作；
为机组的热起动费用；
为机组的冷起动费用。
机组最小技术出力费用仅当机组在时段处于开机状态时才会考虑，可表示为
（4）
式中，
为机组开停机状态0-1变量，=1表示机组在时段处于开机状态，=0表示机组处于停机状态；
为机组的最小技术出力费用。
机组出力表达式为
（5）
（6）
式中，
为机组中标的总段数；
为机组的最小技术出力；
、
分别为机组申报的第个出力区间的上、下界。
2）系统功率平衡约束
（7）
式中，
为系统在时段的总负荷。
3）系统旋转备用约束
（8）
式中，
为机组的最大有功出力；
为系统在时段要求的总备用。
4）机组出力约束
（9）
式中，
为机组的最小有功出力。
5）机组爬坡约束
（10）
（11）
式中，
为机组在时段停机状态0-1变量，=1表示执行停机操作；
、
、
、
分别为机组的功率上升速度限制、功率下降速度限制、起动功率速度限制及停机功率速度限制。
6）机组最小起停约束
（12）
（13）
（14）
（15）
式中，
为机组的初始状态；
、
、
分别为机组的初始运行时间（运行取正值，停机取负值）、最小开机时间及最小停机时间；
、
分别为机组在初始时刻仍需连续运行和停机的时间；
为当前时段之前的时段。
7）逻辑约束
（16）
（17）
（18）
式中，
为机组的冷起动时间。
8）线路安全约束
（19）
式中，
为线路
在时段的有功功率；
、
分别为线路的最大、最小功率。线路上的功率使用功率转移分布因子计算，有
（20）
式中，
为机组所在节点对线路的功率转移分布因子；
为系统中的节点总数；
为节点
对线路的功率转移分布因子；
为节点在时段的负荷。
B&C算法以分支定界理论为基础，通过不断分支（Branching），将原问题的搜索空间生成更小、更容易求解的子问题，即将求解MILP问题转换为求解序列LP问题，在求解过程中又通过收缩MILP问题的上下界找到最优间隙（Gap）小于预设值时的最优解。在B&C算法中，分支策略决定了选择哪个变量进行划分子问题，会对算法性能产生重大的影响[17]。效果好的分支策略能够生成很小的搜索树，快速抬升下界，减少不必要的节点探索。
根节点是B&C算法的起点，当B&C算法在根节点探索阶段没有找到最优解时，它将通过分支来逐步探索可能的搜索空间，这个探索的过程就是B&C算法的分支阶段。
在算法过程中还涉及另外一种重要技术——冲突分析（Conflict Analysis）[18]，它在某个节点不可行或其LP松弛的目标函数值超出上界时，通过构建冲突图（Conflict Graph），分析节点不可行或超出边界的原因，并从冲突图中提取冲突约束用于割平面或域传播，从而收紧搜索树中其他节点的可行域，帮助排除不包含最优解的分支，提高搜索的效率。
SCUC问题中机组只有开机、停机两种状态，故其MILP模型适合使用二元分支策略。二元分支策略通过将分支变量的可行域分为两个部分以得到两个互斥的子节点。
不同的分支策略对应不同的变量评估方法，得出变量在分支时的评估值。变量的评估值越大，往往被认为以它先进行分支产生的效果越好。做出高质量的分支决策通常非常耗时，因此优秀的分支策略通常在决策质量上有所妥协，以求花很少的时间选择出当前的优质变量[19]。由于同一个变量在左右两个分支时的评估值不同，常通过映射函数将两者综合起来得到一个评估值。常用的映射函数有线性评估函数[20]和乘积评估函数[21]，分别为
（21）
（22）
式中，
、
分别为变量的左右分支评估值；
为权重，
；
为很小的正数，通常取10-6。由于乘积评估函数在MILP中的总体表现要优于线性评估函数[22]，故在HiGHS等求解器的分支策略中默认使用乘积评估函数来综合两个分支的评估值。
B&C算法中有三种典型的分支策略：强分支（Strong Branching, SB）[23]、伪成本分支（Pseudocost Branching, PB）[24]及可靠性分支（Reliability Branching, RB）[17]。
2.2.1 强分支
SB的思想是在实际分支前，通过计算所有候选分支LP松弛问题，测试候选分支变量改进下界的能力，并选择改进下界最显著的候选分支变量进行分支。
SB选出了当前“最优”的分支变量，可以产生最小的搜索树。但由于求解所有候选分支变量的LP问题时，若MILP模型很大，会带来巨大的计算负担。它提高分支变量决策质量所带来的收敛收益会被长时间的LP求解所抵消，使B&C算法总的求解效率下降。
2.2.3 伪成本分支
伪成本是指分支变量单位变化量所致目标函数值的变化值。PB是收集求解过程中已分支变量的伪成本来估计当前节点上变量变化对目标函数值的影响，并选择对目标函数值影响最大的变量进行分支。
令
和
分别为在分支定界树中某一节点上将变量
向下及向上分支后，每单位变化时目标函数值在对应分支方向上的变化量，则
（23）
（24）
式中，
为变量的LP松弛解值；j为LP松弛解值不为整数的整数变量的索引；
、
分别为向上或向下分支时目标函数值的变化量。在以作为分支变量的所有节点中，设它们分支生成的左子节点中LP松弛可行的子节点数量为
，生成的右子节点中LP松弛可行的节点数量为
，则分支所导致的目标函数的总变化量
、
分别为
（25）
（26）
则的上、下伪成本
、
分别为
（27）
（28）
变量的伪成本在未初始化时仅为一个很小的值，之后会在B&C算法求解过程中随着分支的进行不断更新。PB通过收集求解过程中已分支变量的伪成本来估计当前节点上变量的变化对目标函数值的影响，并选择对目标函数值影响最大的变量进行分支。变量对目标函数值的影响即为PB评估值，有
（29）
PB是对SB的模仿，具有比SB更高的计算效率。但在分支过程的早期缺乏足够多的已分支变量信息，伪成本分支在这个时期可能具有较差的效果。
2.2.3 可靠性分支
RB结合了SB和PB的优点，是通用分支策略中性能较为优异的策略之一。当变量的分支次数满足式（30）时变量不可靠。
（30）
式中，
为可靠性阈值，
。RB首先检验分支变量的可靠性，若变量可靠则使用变量的PB评估值
作为其RB评估值
，即
（31）
若变量的伪成本未初始化或不可靠，则应用SB来积累一定的分支信息，然后再转为PB快速选择变量。
上述分支策略都是基于MILP的通用数学结构评估出较好的分支变量，并没有利用问题本身的物理特点。在求解SCUC模型中，机组容量、时段等物理模型信息并没有被充分利用。下面提出一种定制化分支策略UPHB，将机组的物理模型参数与经典分支策略相结合，在利用变量数学结构特性的同时体现SCUC的物理模型特点。
单一的分支策略难以在所有问题上有良好的表现，同一MILP问题产生的子MILP问题也是如此。如果在适当的时机采用其他分支策略，就可能提高B&C算法的搜索效率[25]。因此，UPHB的目的是结合不同变量选择规则的优势加速问题求解，由主要与次要变量选择规则及变量选择规则的切换策略组成。
在传统分支策略中，所有整数变量都有可能被选为分支变量，对SCUC问题来说可能会生成不必要的节点，从而降低求解效率。SCUC的目的是获取机组多时段开停机计划，而机组的开停机状态0-1变量直接反映了机组的运行状态，且其他三类0-1变量均与相关，确定后即可根据逻辑约束式（16）～式（18）推断其他三类0-1变量的值。因此与其他三类0-1变量相比，在上分支对求解效率的影响更大。
故与传统分支策略不同，本文认为在分支策略中比其他三类0-1变量更重要，在分支策略中只将作为候选分支变量。如何从候选分支变量中选择分支变量即为分支策略的变量选择规则，不同的分支变量选择方式构成不同的变量选择规则。
3.2.1 容量混合规则
机组的容量是机组众多参数中非常重要的一个物理参数。在电力系统中，承担基荷的机组通常是容量较大的机组，与小容量机组相比，这些大容量机组往往具有更好的经济性。一些优先顺序法也将机组容量作为机组优先级排序的重要指标，如文献[26]以机组容量大小作为优先顺序表的参考来获得初始解，然后通过一系列操作调整机组状态，从而快速获得可行解。当分支策略优先决策大容量机组的状态时，随着搜索深度的增加，这些额外的机组状态调整操作将会在B&C算法不断分支的过程中自动完成，有助于B&C算法快速找到可行解。
此外，使用通用分支策略的B&C算法难以精准地定位到SCUC问题的关键区域。与小容量机组相比，大容量机组对系统功率平衡的影响更大，对问题的可行性和成本的影响更显著。当采用B&C算法确定大容量机组的状态后，就能够迅速剪除大量无法满足负荷需求或违反约束的机组状态组合，从而有效缩减问题的可行解空间。因此，分支策略应该优先确定大容量机组的运行状态，优先考虑将大容量机组的作为分支变量来引导B&C算法尽早确定关键决策，提高求解效率。
通用分支策略的评估值实际上已经涵盖了MILP模型的整体信息，但还不足以突出SCUC的部分物理参数对分支的重要影响。为了使算法简单有效，本文只选择将容量和时段两个主要因素叠加到评估值上。在RB的基础上，将机组容量作为权重，为变量定义评估函数
，有
（32）
式中，
为基准容量；
为变量的RB估值。在考虑机组容量的同时还保留了变量在MILP数学结构中的信息。
此外，SCUC是一个多时段的优化调度问题，前面时段的决策会对后面时段产生重要影响，在选择分支变量时应该将时序考虑在内。本文先按容量混合规则为变量计算评估值，然后根据从大到小的顺序对变量进行排序，若评估值最大的多个候选分支变量评估值相同，则在这些变量中选择所在时段最小的变量作为分支变量。容量混合规则示意图如图1所示。
图1 容量混合规则示意图
Fig.1 Schematic of capacity hybrid rule
式（32）中，由B&C算法在整个求解过程中收集到的与变量有关的数学结构求解信息计算得到，是在单个节点上无法获取的全局信息，体现了变量在求解过程中分支的最优性，而机组的容量也在一定程度上反映了变量的重要程度，故具有一定的贪婪属性，这可能导致在连续的多个节点上都按照固定的优先顺序选择分支变量，不符合贪婪规则的有用节点可能被错过。这使得后续分支生成的子节点可能有相似的LP松弛最优解，很容易陷入局部最优，导致B&C算法的Gap下降很慢甚至不发生变化，故需要在适当的时机切换变量选择规则来改变搜索方向，以增加跳出局部最优的概率。
3.2.2 平均费用规则
为了解决容量混合规则可能导致陷入局部最优的问题，提出了平均费用规则。
由式（1）、式（2）和式（4）可知，SCUC模型的目标函数值大小与0-1变量及连续变量相关。对进行分支将直接改变目标函数值，目标函数值的变化量与机组的最小技术出力费用有关，不需要计算就可以直接得到。而的变化对目标函数值的影响与伪成本一样需要求解子节点的LP松弛，具有较大的计算负担，故平均费用规则只考虑。为了获得目标函数值更小的可行解，大的机组应该比小的机组优先级低。但为了改变B&C算法的搜索方向从而跳出局部最优，应优先决策大的机组。因此，利用机组的、的LP松弛解及乘积评估函数定义的评估函数为
式中，
为在当前节点的LP松弛解值。为了选择作为分支变量的次数较少的变量，在时序上平均费用规则采用与容量混合规则不同的选择分支变量的方式：首先从候选分支变量集中挑选出所在时段最小的变量，然后从这些时段最小的变量中选择得分最大的变量作为分支变量。平均费用规则示意图如图2所示。
图2 平均费用规则示意图
Fig.2 Schematic of average cost rule
平均费用规则选择的分支变量往往不符合容量混合规则的贪婪规则，因此将其运用到容量混合规则中能够使B&C算法向不符合贪婪规则的其他区域搜索，从而增加算法搜索路径的多样性，帮助发现潜在的更优解。
在同时段下，越大、越接近0.5，
越大，变量被选为分支变量的优先级越高，这与传统分支策略中的最不可行分支（Most Infeasible Branching, MIB）和最小不可行分支（Least Infeasible Branching, LIB）类似。MIB、LIB的效果并不比随机选择一个分支变量好多少，故由平均费用规则生成的子节点质量较差[21]。由平均费用规则生成的右子节点由于
被固定为1，使子节点产生较大的目标函数值增量，同时还可能压缩更经济的机组的出力空间。因此这些子节点不可行或其局部下界超出全局上界的概率较高，尤其是在Gap较小时，子节点的局部下界很容易越界，这反而可以为下一步的分支提供非常有用的信息。冲突分析技术能够利用这些信息进一步缩小问题的搜索空间，避免较差分支的反复探索。平均费用规则的另一个作用就是尽可能选择能够生成被利用的子节点的分支变量，为B&C算法提供有利于加速求解的信息。
UPHB将容量混合规则与平均费用规则相结合，以平均费用规则生成的质量较差节点所需的负担为代价来换取B&C算法整体求解效率的提高。虽然使用平均费用规则选择的分支变量越多，生成的能够被冲突分析利用的节点就越多，但同样会增加需进一步分支探索的节点数量，可能会降低求解效率，因此需要控制其选择的分支变量数量。
UPHB的主要变量选择规则使用次数最多、最频繁，在很大程度上决定了UPHB的效率；次要变量选择规则起到辅助作用，只在特定情况下少量使用。根据以上对容量混合规则及平均费用规则的描述，容量混合规则倾向于选择分支效果较好的分支变量，将其作为主要变量选择规则；平均费用规则倾向于改变B&C算法的搜索方向并提供有利于求解的信息，将其作为次要变量选择规则。
变量选择规则的切换策略决定了UPHB更改其使用的变量选择规则的时机，可以控制UPHB使用两种变量选择规则选择分支变量的频率和数量。UPHB中变量选择规则的切换由B&C算法在分支时的Gap和已经探索的节点数量决定。若B&C算法的Gap在一段时间内没有变化，说明B&C算法可能陷入了局部最优，需要改变搜索方向，此时将UPHB的容量混合规则切换为平均费用规则。当B&C算法使用平均费用规则探索了少量的节点后，无论其Gap是否变化都将变量选择规则切换至容量混合规则。
UPHB的具体步骤如算法1所示，其中
为全局变量，指示UPHB当前使用的变量选择规则。当
时表示UPHB使用容量混合规则，否则表示UPHB使用平均费用规则。
为B&C算法当前探索的节点数；
、
分别记录UPHB判断是否切换变量选择规则时B&C算法探索的节点数与Gap；
为常数；
，用于控制UPHB切换变量选择规则的时机；
、
分别为B&C算法当前的全局上界和下界；
为分支变量；函数CHR()、AVR()分别为使用容量混合规则及平均费用规则选择并返回分支变量。
算法1 UPHB 输入：MILP问题 输出：分支变量 1）if 2） if 3） =CHR() 4） else 5） 6） if 7） 8） =CHR() 9） else 10） 11） =ACR() 12） endif 13） endif 14） else 15） if 16） =ACR() 17） else 18） 19） 20） 21） =CHR() 22） endif 23） endif 24）返回
的大小决定了变量选择规则的切换频率及使用次数，不同规模的系统需要取不同的值。在B&C算法求解的早期即Gap较大时，变量的可靠性不高，UPHB应多使用容量混合规则来固定大容量机组的，在收集相应变量信息使变量可靠的同时帮助B&C算法尽快找到可行解。B&C算法在求解过程的中后期容易遇到Gap下降缓慢的问题，此时可以增加切换变量选择规则的频率，通过改变搜索方向及获取额外的信息来跳出局部最优。因此应在求解过程中动态变化，的值为
（34）
（35）
式中，w为小于1的正数。
B&C算法在开始分支时就能够获得较小的Gap，因此
的值不会很大。随着求解的进行，将随着Gap的减小而减小，变量选择规则的切换频率也将越来越高。UPHB虽然更频繁地使用平均费用规则选择分支变量，但平均费用规则选择的分支变量数量也越来越少，在合理的
值下容量混合规则选择的分支变量在数量上仍然占多数。
高度依赖变量在求解过程中被分支时所产生的信息，当B&C算法收集到的变量信息有限时将不可靠。使用计算评估值的容量混合规则也面临同样的问题，这就需要可靠性分支策略对不可靠的评估值进行初始化。
由于本文只选择
作为分支变量，故其他三类0-1变量在求解的任何时期都是不可靠的。如果使用传统的可靠性分支策略，则每次分支时必定会对其他三类0-1变量应用SB，但UPHB不会选择其他三类0-1变量作为分支变量，这就导致因B&C算法反复求解无效的LP而降低求解效率。故本文对传统可靠性分支做出改进，只在变量选择规则选择出分支变量后检验分支变量的可靠性，并根据变量可靠性决定是否对分支变量应用SB。
为了验证本文所提出的混合分支策略的有效性，对IEEE 118节点系统、RTE 1888节点系统、Polish 2383节点系统进行仿真计算，各系统数据来源于MATPOWER[27]。在开源求解器HiGHS 1.6.0上定制MILP模型的分支算法。HiGHS部署在Intel(R) Core(TM) i7-10700计算机上，收敛间隙设置为0.01%，其他参数均使用默认设置。
除了使用PB、RB及UPHB进行性能测试外，还与另外两种分支策略进行对比，分别为：①容量混合分支（Capacity Hybrid Branching, CHB）策略，使用容量混合规则选择分支变量，不切换变量选择规则；②平均费用分支（Average Cost Branching, ACB）策略，使用平均费用规则选择分支变量，不切换变量选择规则。
在测试时HiGHS求解器只启用一种分支策略，其他分支策略被关闭不生效。CHB、ACB与UPHB相同，只将机组开停机状态0-1变量作为候选分支变量，CHB和UPHB只对不可靠的机组开停机状态0-1变量应用SB。
为了研究权重的不同取值对UPHB求解的影响，使用具有不同值的UPHB求解RTE1888节点系统，的步长为0.2，求解结果见表1。
表1 RTE 1888节点系统中不同
值的UPHB计算结果
Tab.1 UPHB computation results with varying values in the RTE 1888-bus system
α求解时间/s选择分支变量数量规则切换次数 容量混合规则平均费用规则 0.16 9179658614 0.36 15686014314 0.56 20880822214 0.77 2871 23128316 0.96 8981 25754729
由表1可知，当变大时，UPHB使用平均费用规则选择的分支变量数量整体上也呈现上升趋势，但模型的求解时间并不总是随的增加而增加。当
时，平均费用规则生成的节点中能够提供有用信息的较少，求解时间较长。当
和0.5时，平均费用规则生成的节点较多，可以为B&C算法提供足够多的有用信息。这些信息为B&C算法节约的时间大于探索这些节点所用的时间，因此求解时间较短。又由于生成的质量较差节点较多，B&C算法在探索这些节点时的Gap可能不会变化，所以此时UPHB的规则切换次数较大，正好与时相同。当
时，平均费用规则生成的有用节点占比变小，探索这些节点带来的总收益下降，因此求解时间和规则切换次数均增加。但当
时平均费用规则选择的分支变量数比
时大，求解时间却相对较短。这是由于时虽然平均费用规则生成的无用节点较多，但每轮获得的有用节点累积到一定程度时加速了B&C算法的后续求解。由于=0.3时效果最好，因此下面使用进行仿真。
下面使用具有不同分支策略的HiGHS求解器求解IEEE 118节点系统、RTE 1888节点系统及Polish 2383节点系统，求解结果见表2及图3。表2和图3分别展示了求解器使用不同分支策略时求解三个系统所需要的时间及探索的节点总数。为了更好地体现不同分支策略的性能，表2中“rsp”是以RB的计算结果为基准，不同分支策略的求解时间相对于RB的减少比例，具体定义为
（36）
式中，
为求解器使用RB时的求解时间；tB为求解器使用其他分支策略时的求解时间。速度提升比例为正说明该分支策略的求解时间比RB短，为负则说明其求解时间比RB长。
表2 不同系统下求解器使用不同分支策略的计算结果
Tab.2 The computational results when the solver using each branching strategy in different systems
分支策略IEEE 118 RTE 1888Polish 2383 tB/srsp(%)tB/srsp(%)tB/srsp(%) RB91—15 451—6 345— PB116-28.913 30313.97 662-20.8 CHB6527.88 44145.43 21249.4 ACB752-735.615 3290.820 099-216.8 UPHB4846.76 15660.22 35962.8
图3 不同系统下求解器使用各分支策略时探索节点数
Fig.3 Number of nodes explored by the solver using each branching strategy under different systems
由表2及图3可知，CHB的求解速度与RB相比提高了27%～49%，性能较好；ACB的求解速度与RB相比大幅下降，性能较差。因此，根据第3节的描述，将容量混合规则作为UPHB的主要变量选择规则、平均费用规则作为次要选择规则是合理的。
求解器使用UPHB时的计算效率除了比RB高外，与CHB相比也得到了进一步提升，求解IEEE 118节点系统、RTE 1888节点系统及Polish 2383节点系统花费的时间与CHB相比分别下降了26.2%、27.1%、26.6%，与RB相比则下降了46.7%、60.2%、62.8%，所需探索的节点数在所有分支策略中也最少，具有最小的搜索树。这表明UPHB切换变量选择规则是有效的，在变量选择规则和规则切换策略的共同作用下取得了良好的分支效果。UPHB引入的平均费用规则为B&C算法提供了容量混合规则不曾提供的有用信息，这些信息能够缩小问题的搜索空间，帮助B&C算法剪枝，为B&C算法带来的部分收益就能够补偿探索平均费用规则生成的较差节点所带来的额外时间开销，在保留CHB优势的同时对B&C算法产生了积极的影响，进一步提升了B&C算法求解SCUC问题的效率。
表3展示了求解器使用不同分支策略求解RTE 1888节点系统时求解器的根节点探索阶段与分支阶段所花时间及在总求解时间中的比例。表3中，根节点探索阶段所花费的时间为使用该分支策略求解时求解器探索根节点所花费的时间与由于重启动导致的求解器重新探索根节点所花费的时间之和；分支阶段所花费的时间等于总求解时间减去根节点探索阶段花费的时间；时间占比表示各阶段花费的时间在总求解时间中的比例。与根节点探索阶段相比，分支阶段的时间占比越小，求解器探索问题搜索空间的效率越高，分支策略的效果越好。由表3可知，在五种分支策略中，使用UPHB时求解器的分支阶段时间占比最低，求解器在分支搜索过程中花费的时间也最少，说明UPHB与其他分支策略相比具有较好的分支效果，可以加快B&C算法的搜索过程。
表3 RTE 1888节点系统下不同分支策略分支时间占比
Tab.3 Percentage of branching time of different branching strategies for the RTE 1888-bus system
分支策略根节点探索阶段分支阶段 tB/s时间占比(%)tB/s时间占比(%) PB2 03915.311 26484.7 RB1 98112.813 47087.2 CHB1 90222.56 53977.5 ACB2 73817.912 59182.1 UPHB2 15835.03 99965.0
图4～图6分别展示了HiGHS求解器使用经典分支策略RB、LIB、PB求解IEEE 118、RTE 1888及Polish 2383节点系统时所有分支变量中四类0-1变量的数量分布。图中，u、y、z、yc分别表示机组开停机状态0-1变量、机组启动0-1变量、机组停机0-1变量以及机组冷启动0-1变量。虽然RB、LIB、PB将四类0-1变量都作为候选分支变量，但从求解三个系统的分支结果可以看到，RB、LIB、PB选择的分支变量中的数量仍然占据多数。除了求解器使用LIB求解IEEE 118节点系统与Polish 2383节点系统的情况外，其余情况下求解器使用三种分支策略求解时分支变量中的数量占比均超过了50%且远大于其他三类0-1变量，说明这三种分支策略更倾向于选择变量作为分支变量，同时这也表明在MILP的数学结构上同样具有分支最优性。
图4 IEEE 118节点系统中求解器使用不同分支策略时四类0-1变量在分支变量中的次数占比
Fig.4 The percentage of occurrences for four types of binary variables among branching variables under different branching strategies in the IEEE 118-bus system
图5 RTE 1888节点系统中求解器使用不同分支策略时四类0-1变量在分支变量中的次数占比
Fig.5 The percentage of occurrences for four types of binary variables among branching variables under different branching strategies in the RTE 1888-bus system
为了进一步验证机组开停机状态0-1变量
的重要性，使用具有不同候选分支变量集的经典分支策略RB、LIB及PB求解Polish 2383节点系统，求解结果见表4。表4中，“原始”表示将四类0-1变量作为候选分支变量集的原始经典分支策略，“定制”表示只将作为候选分支变量集的经典分支策略。由表4可知，RB、LIB及PB将由四类0-1变量组成的候选分支变量集更换为只包含的集合后的求解速度均有不同程度的提升。更换候选分支变量集前求解越慢的分支策略，在更换候选分支变量集后求解速度的提升越大，可见分支变量的类型对B&C算法求解SCUC问题的效率有一定的影响，只将作为分支变量是合理的。
图6 Polish 2383节点系统中求解器使用不同分支策略时四类0-1变量在分支变量中的次数占比
Fig.6 The percentage of occurrences for four types of binary variables among branching variables under different branching strategies in the Polish 2383-bus system
表4 Polish 2383节点系统中使用不同候选分支变量集的经典分支策略的求解结果
Tab.4 Solving results of classical branching strategy with different candidate branching variable sets in the Polish 2383-bus system
策略类型RBLIBPB tB/s节点数tB/s节点数tB/s节点数 原始6 3458 9028 37724 7297 78315 950 定制5 79113 8525 77617 2166 43510 396
表5为不同情况下UPHB求解Polish 2383节点系统的求解结果。表5中，“UPHB_all”表示将四类0-1变量均作为候选分支变量且使用可靠性策略的UPHB，“UPHB_noSB”表示只将机组开停机状态0-1变量作为候选分支变量但不使用可靠性策略的UPHB。“分支次数”表示四类0-1变量被选为分支变量的次数，“总次数”表示分支总次数。由表5可知，当使用UPHB_all时，求解器的总求解时间、探索的节点数、分支次数与UPHB相比均大幅提升，同样表明只选择机组开停机状态0-1变量作为分支变量是有效的。此外，UPHB_noSB与UPHB_all类似，各项指标与UPHB相比均显著增加，说明除分支变量的类型外，变量的可靠性策略也能够大幅减少B&C算法的分支次数及探索的节点数，提高求解速度，因此可靠性策略也对B&C算法的效率有很大的影响。
表5 Polish 2383节点系统下不同UPHB的求解结果
Tab.5 Solving results of different UPHB for the Polish 2383-bus system
分支策略tB/s节点数分支次数 uyzyc总次数 UPHB2 3592 0101 8270001 827 UPHB_all4 86417 45710 9091661 9802 53815 593 UPHB_noSB9 41311 0488 2090008 209
图7为分别使用分支策略PB、RB、UPHB求解Polish 2383节点系统时B&C算法的Gap随时间变化的曲线。图7中只展示Gap在1%以内时的变化情况，此时所有B&C算法都已处于分支阶段。由图7可知，使用分支策略PB、RB时，B&C算法在其Gap小于0.5%时遇到了很明显的收敛瓶颈，在相当长的一段时间内Gap都下降得很慢，在部分时间段内甚至不发生变化，这意味着在这些时间段内B&C算法探索的节点没能有效改进其上、下界，分支效果较差。
图7 Polish 2383节点系统下不同分支策略的Gap随时间变化曲线
Fig.7 Gap curves of different branching strategies for the Polish 2383-bus system
虽然B&C算法使用CHB作为分支策略能大幅提高求解SCUC问题的速度，能够很快收敛，但与使用RB及PB时一样，存在Gap在一段时间内基本维持不变的现象，即陷入了局部最优。而UPHB将容量混合规则切换为平均费用规则得以改变这一状况，使B&C算法的Gap在维持了一段时间后迅速下降。这说明UPHB具有良好的改进上、下界的能力，通过变量选择规则切换策略引入的平均费用规则起到了积极作用，在改变B&C算法搜索方向的同时为B&C算法提供了有利于求解的信息，打破了CHB的Gap下降瓶颈，加速了B&C算法的收敛。这体现了UPHB将问题向最优的方向引导的能力，同时也体现了将多种变量选择规则结合使用具有很大的优势和潜力。
以当前Polish 2383节点系统的负荷曲线为基准，在[0.8, 1.2]之间随机选取5个值作为基准负荷曲线的比例系数，进而生成5条新的负荷曲线，并重新建立模型。新模型以2383-1～2383-5表示。使用RB、CHB、UPHB三种分支策略分别对5个新模型进行求解，求解结果见表6及图8。与RB相比，使用CHB与UPHB时的求解速度分别平均提升了36.0%与60.5%。除了测试系统2383-2外，UPHB求解其余测试系统所需要探索的节点数均比RB及CHB少。这表明UPHB切换变量选择规则起到了积极作用，进一步提高了CHB的分支效果。
表6 具有不同负荷曲线的Polish 2383节点系统的求解结果
Tab.6 Solving results for the Polish 2383-bus system with varying load curves
测试系统RBCHBUPHB tB/srsp(%)tB/srsp(%)tB/srsp(%) 2383-17 490—4 20043.92 22470.3 2383-214 025—9 45232.65 36161.8 2383-328 470—15 88844.29 41266.9 2383-44 889—3 60926.22 45049.9 2383-515 063—10 06033.27 01453.4
图8 求解不同负荷曲线下Polish 2383节点系统探索的节点数
Fig.8 Number of explored nodes for the Polish 2383-bus system under different load curves
本文结合物理模型0-1变量类型、机组的容量、费用及SCUC问题的时序等特点提出了两种变量选择规则用于选择分支变量。在两种变量选择规则的基础上，提出一种混合分支方法对HiGHS求解器的分支策略进行定制。仿真结果表明，该混合分支方法具有良好的分支效果，能够产生较小的搜索树，显著减少求解器探索的节点，大幅度地提高开源HiGHS求解器求解SCUC问题的效率。
在开源HiGHS求解器上根据物理模型的特点定制化开发SCUC的专用求解器，为突破电力现货市场出清的“卡脖子”问题提供了一个新的思路。此外，虽然定制化后的开源求解器与商业求解器在求解效率上还有一定的差距，但这一定制化的思路也能为商业求解器性能的继续改进提供新的解决方案。
本文的定制化思路只结合了求解器中的分支策略，未来将在HiGHS求解器上结合其他求解加速策略进行定制。
参考文献
[1] 向明旭, 陈泓霏, 曹晓峻, 等. 省间电力中长期交易出清问题多解顺次寻优的高效计算方法[J]. 电工技术学报, 2025, 40(11): 3545-3559. Xiang Mingxu, Chen Hongfei, Cao Xiaojun, et al. Efficient sequential optimization method for inter-provincial medium-and long-term power transaction clearing problem under multiple-solution scenarios[J]. Transactions of China Electrotechnical Society, 2025, 40(11): 3545-3559.
[2] 高倩, 杨知方, 李文沅. 电力系统混合整数线性规划问题的运筹决策关键技术综述与展望[J]. 电工技术学报, 2024, 39(11): 3291-3307. Gao Qian, Yang Zhifang, Li Wenyuan. Prospect on operations research for mixed-integer linear programming problems in power systems[J]. Transactions of China Electrotechnical Society, 2024, 39(11): 3291-3307.
[3] 陈启鑫, 房曦晨, 郭鸿业, 等. 电力现货市场建设进展与关键问题[J]. 电力系统自动化, 2021, 45(6): 3-15. Chen Qixin, Fang Xichen, Guo Hongye, et al. Progress and key issues for construction of electricity spot market[J]. Automation of Electric Power Systems, 2021, 45(6): 3-15.
[4] Chen Yonghong, Casto A, Wang Fengyu, et al. Improving large scale day-ahead security constrained unit commitment performance[J]. IEEE Transactions on Power Systems, 2016, 31(6): 4732-4743.
[5] 付聪, 王砚平, 刘俊磊, 等. 基于辅助优化问题的安全约束机组组合约束削减方法[J]. 电力系统保护与控制, 2021, 49(21): 9-17. Fu Cong, Wang Yanping, Liu Junlei, et al. Constraint reduction method for security-constrained unit commitment based on an auxiliary optimization problem[J]. Power System Protection and Control, 2021, 49(21): 9-17.
[6] 袁泉, 孙宇军, 张蔷, 等. 考虑安全约束耦合辨识的日前发电计划求解[J]. 电力系统自动化, 2022, 46(21): 143-151. Yuan Quan, Sun Yujun, Zhang Qiang, et al. Day-ahead generation schedule solving considering identification of security constraint coupling[J]. Automation of Electric Power Systems, 2022, 46(21): 143-151.
[7] 王进, 张粒子, 丛野, 等. 应用图论建模输电网的电力现货市场出清模型[J]. 中国电机工程学报, 2024, 44(9): 3429-3440. Wang Jin, Zhang Lizi, Cong Ye, et al. A clearing model of electricity spot market based on graph theory to modeling transmission network[J]. Proceedings of the CSEE, 2024, 44(9): 3429-3440.
[8] Chen Yonghong, Pan Feng, Holzer J, et al. A high performance computing based market economics driven neighborhood search and polishing algorithm for security constrained unit commitment[J]. IEEE Transactions on Power Systems, 2021, 36(1): 292-302.
[9] Ma Ziming, Zhong Haiwang, Xia Qing, et al. A unit commitment algorithm with relaxation-based neig-hborhood search and improved relaxation inducement[J]. IEEE Transactions on Power Systems, 2020, 35(5): 3800-3809.
[10] 颜心斐, 钟海旺, 朱灏翔, 等. 基于系统约束诱导割平面的机组组合加速求解算法[J]. 电网技术, 2025, 49(3): 1155-1165. Yan Xinfei, Zhong Haiwang, Zhu Haoxiang, et al. Inducing cutting planes for system constraints to accelerate network-constrained unit commitment[J]. Power System Technology, 2025, 49(3): 1155-1165.
[11] 钟海旺, 虞泽宽, 王孟昌, 等. 电力系统优化求解引擎构建及应用[J/OL]. 电力系统自动化, 2025: 1-11. (2025-11-26)[2025-12-13]. https://link.cnki.net/ urlid/32.1180. TP.20251125.1656.006. Zhong Haiwang, Yu Zekuan, Wang Mengchang, et al. Construction and application of power system optimization engine[J/OL]. Automation of Electric Power Systems, 2025: 1-11. (2025-11-26)[2025-12-13]. https:// link.cnki.net/urlid/32.1180.TP.20251125. 1656.006.
[12] 李佩杰, 万海涛, 赵晓慧, 等. 定制化求解机组组合混合整数线性规划模型的固定—推断法[J]. 电力系统保护与控制, 2023, 51(2): 11-21. Li Peijie, Wan Haitao, Zhao Xiaohui, et al. A customized fix and implicate method for mixed integer linear programming models of unit commitment problems[J]. Power System Protection and Control, 2023, 51(2): 11-21.
[13] Li Peijie, Liao Changtao, Qi Junjian, et al. User-induced heuristics for security-constrained unit commitment: variable influence diving and variable significance neighborhood search[J]. IEEE Transactions on Power Systems, 2025, 40(4): 3334-3346.
[14] 李佩杰, 卢胜津, 李凌昊, 等. 基于分析中心理论的安全约束机组组合问题启发式方法研究[J/OL]. 电网技术, 2025: 1-13. (2025-06-04)[2025-12-13]. https: //doi.org/10.13335/ j.1000-3673.pst.2025.0206. Li Peijie, Lu Shengjin, Li Linghao, et al. A Heuristic method for solving security constrained unit commitment problem based on analysis center[J/OL]. Power System Technology, 2025: 1-13. (2025-06-04) [2025-12-13]. https://doi.org/10.13335/j.1000-3673. pst.2025.0206.
[15] Huangfu Q, Hall J A J. Parallelizing the dual revised simplex method[J]. Mathematical Programming Computation, 2018, 10(1): 119-142.
[16] 邓俊, 韦化, 黎静华, 等. 一种含四类0-1变量的机组组合混合整数线性规划模型[J]. 中国电机工程学报, 2015, 35(11): 2770-2778, 15. Deng Jun, Wei Hua, Li Jinghua, et al. A mixed-integer linear programming model using four sets of binary variables for the unit commitment problem[J]. Proceedings of the CSEE, 2015, 35(11): 2770-2778, 15.
[17] Achterberg T, Koch T, Martin A. Branching rules revisited[J]. Operations Research Letters, 2005, 33(1): 42-54.
[18] Achterberg T. Conflict analysis in mixed integer programming[J]. Discrete Optimization, 2007, 4(1): 4-20.
[19] Huang Mengyu, Huang Lingying, Zhong Yuxing, et al. MILP acceleration: a survey from perspectives of simplex initialization and learning-based branch and bound[J]. Journal of the Operations Research Society of China, 2025, 13(1): 1-55.
[20] Linderoth J T, Savelsbergh M W P. A computational study of search strategies for mixed integer programming[J]. INFORMS Journal on Computing, 1999, 11(2): 173-187.
[21] Achterberg T. Constraint integer programming[D]. Berlin: Technische Universität, 2007.
[22] Achterberg T. SCIP: solving constraint integer programs[J]. Mathematical Programming Computation, 2009, 1(1): 1-41.
[23] Applegate D, Bixby R, Chvatal V, et al. Finding cuts in the TSP (A preliminary report)[R]. Center for Discrete Mathematics & Theoretical Computer Science, 1995.
[24] Benichou M, Gauthier J M, Girodet P, et al. Experiments in mixed-integer linear programming[J]. Mathematical Programming, 1971, 1(1): 76-94.
[25] Di Liberto G, Kadioglu S, Leo K, et al. DASH: dynamic approach for switching heuristics[J]. European Journal of Operational Research, 2016, 248(3): 943-953.
[26] Senjyu T, Shimabukuro K, Uezato K, et al. A fast technique for unit commitment problem by extended priority list[J]. IEEE Transactions on Power Systems, 2003, 18(2): 882-888.
[27] Zimmerman R D, Murillo-Sánchez C E, Thomas R J. MATPOWER: steady-state operations, planning, and analysis tools for power systems research and education[J]. IEEE Transactions on Power Systems, 2011, 26(1): 12-19.
Abstract The security constrained unit commitment (SCUC) problem plays a critical role in ensuring the fairness and economic efficiency of electricity spot market transactions. In electricity market clearing, SCUC is typically formulated as a mixed integer linear programming (MILP) model, whose solution efficiency heavily depends on the performance of commercial MILP solvers. With the expanding trading scope of the electricity spot market, it becomes increasingly difficult for generalized mixed integer programming solvers to solve large-scale security constrained unit commitment models. With the original intention of solving the bottleneck problem of commercial solver, this study develops a hybrid branching method by exploiting distinctive features of the SCUC physical mode—including binary variable types, generator capacities, temporal sequencing patterns, and cost structures—to customize the branching strategy of the open‑source HiGHS solver. The proposed method consists of variable selection rules and a rule switching strategy.
The variable selection rule integrates two complementary components: the capacity hybrid rule and the average cost rule. The capacity hybrid rule integrates unit capacity into the evaluation value of candidate branching variables as weighting factors while resolving decision conflicts among equally evaluation values variables through temporal precedence. When multiple candidate branching variables have identical evaluation scores, those from earlier time intervals are assigned higher branching priority. This dual mechanism accounts for both the magnitudes of evaluation and the different impacts of the temporal interdependencies across multi-interval decision horizons. The capacity hybrid rule serves as the primary variable selection rule within the hybrid branching method and largely dictates its overall efficiency. Unit costs and temporal characteristics are incorporated into the average cost rule, where variables with maximal evaluation values are selected among minimum-cost candidates. This rule has a high probability of generating nodes that can be pruned, diversifies the search paths of the Branch-and-Cut (B&C) algorithm and provides useful information for it, and as a supplementary component within the hybrid branching method.
The rule switching strategy determines the switching conditions between the capacity hybrid rule and the average cost rule for the bottleneck problem of the gap reduction in the branch process. This enables dynamic adjustment of the branching variable selection logic during the solving process through the strategic alternation of variable selection rules. When stagnation in the optimality gap reduction is detected, the hybrid branching method automatically switches the active variable selection rule to steer the B&C algorithm away from local optima. Furthermore, the hybrid branching method refines the candidate branching variable set by filtering variables according to the physical characteristics implied by binary variable types and customizes the application of strong branching to address reliability issues in the branching evaluation scores of candidate branching variables. Simulation results from the IEEE 118 bus, RTE 1888 bus, and Polish 2383 bus systems demonstrate that using the capacity hybrid rule alone without any rule switching for variable selection improves the speed of the HiGHS solver for SCUC problems by 27% to 49%. When the hybrid branching method dynamically switches variable selection rules, the solving efficiency of HiGHS is further enhanced, achieving an overall speedup of 46% to 62% compared to its original performance. The proposed customized method provides a new idea for the development of an independent and controllable security constrained unit commitment solver in China.
keywords：Security constrained unit commitment, mixed integer linear programming, solver, branching method, open source
DOI: 10.19595/j.cnki.1000-6753.tces.250683
中图分类号：TM73
国家自然科学基金（52267006）和广西创新驱动发展专项资金（桂科AA19254034）资助项目。
收稿日期 2025-04-24
改稿日期 2025-12-22
李佩杰 男，1984年生，博士，副教授，研究方向为电力系统最优运行等。E-mail：lipeijie@gxu.edu.cn
葛佳伟 男，1999年生，硕士研究生，研究方向为电力系统最优运行等。E-mail：1367678967@qq.com（通信作者）
（编辑 赫 蕾）