1. 引言

机组组合(Unit commitment, UC)是电力系统规划和运行中的一类重要问题，其目标为在满足电力系统要求和机组技术限制的情况下，最小化系统总运行成本。该问题为复杂的大规模混合整数二次规划(Mixed integer quadratic programming, MIQP) [1]。

几十年来，研究人员针对UC问题已提出诸多求解方法，这些方法大致可分为人工智能算法和数学优化算法。人工智能算法主要包括粒子群优化算法[2]、遗传算法[3]、模拟退火算法[4]、进化算法[5]和人工神经网络算法[6]等。人工智能算法属于随机搜索方法，容易陷入局部最优解，计算效率不能得到稳定的保障。数学优化算法主要包括分支定界法(Branch and bound, BB) [7] [8]、优先顺序(Priority list, PL) [9] [10]、动态规划法(Dynamic programming, DP) [11]、拉格朗日松弛算法(Lagrangian relaxation, LR) [12] [13]、Benders分解法(Benders decomposition, BD) [14]、外逼近法(Outer approximation, OA) [15]、内外逼近法(Outer-inner approximation, OIA) [16]、交替方向乘子法(Alternating direction method of multipliers, ADMM) [17]和混合整数线性规划法(Mixed integer linear programming, MILP) [18]-[20]。数学优化算法作为求解UC问题的经典算法，多年来在求解UC问题上已得到广泛应用。其中，PL法是优先投入最经济的机组来满足UC问题的约束条件，收敛速度快。DP法通过搜索机组启停状态形成的解空间来寻求UC问题的最优解，可得到中等规模UC问题的全局最优解。LR法将UC问题分解为若干单机组子问题进行求解，避免了决策变量过多造成的困难，可获得质量较好的次优解。BD法将所求解问题分解为主问题和子问题进行交替求解，并在求解过程中加入可行割平面或最优割平面，以加快问题的求解速度。OA法和OIA法与BD法类似，都是将原问题分解为相对容易求解的主问题和子问题，从而得到UC问题高质量的可行解。MILP法致力于将UC问题近似为MILP模型，可在合理时间内获得UC问题的高质量次优解。由于混合整数规划求解器求解能力的飞速提高，MILP法成为目前求解UC问题的主流方法。

BB法通过求解一系列由原问题剖分形成的子问题来获得所求问题的全局最优解。它最初由Land和Doig在文献[21]中提出，该方法是通过松弛、分支、定界和剪枝进行求解。但BB法本质上是一种枚举法，其计算时间随问题规模呈指数式变化。为提高BB法的计算效率，人们围绕确定上下界策略进行了深入研究，包括割平面、预处理和启发式等[22] [23]。文[8]提出一种求解UC问题的BB法，不考虑机组的优先顺序，可直接处理和时段相关联的启动费用，并且能处理随机备用约束。文[24]考虑了机组备用和电力交易合同问题，并采用BB法求解。

本文利用热率和透视割平面将机组组合模型做近似线性化处理，将混合整数二次规划转化为混合整数线性规划进行求解。为提高BB法的计算效率，进行上层变量固定并优先搜索机组启停状态最接近0.5的节点。数值结果表明，此法与直接求解混合整数二次规划的发电费用相当，但从时间方面来看优势明显，适合求解大规模机组组合问题。

2. UC问题的数学模型

UC问题的目标函数为：

$\min F={\displaystyle \sum _{t=1}^T{\displaystyle \sum _{i=1}^N\left[f_i\left(u_{i,t},P_{i,t}\right)+C_{i,t}\right]}}$ (1)

其中，T为研究时段数；N为研究机组数；0~1变量$u_{i,t}$ 为机组i在t时段的运行状态，值为1时为运行状态，值为0时为停机状态；$f_i\left(u_{i,t},P_{i,t}\right)={\alpha }_i{u}_{i,t}+{\beta }_i{P}_{i,t}+{\gamma }_i{\left(P_{i,t}\right)}^2$ 为机组i在t时段的煤耗成本，${\alpha }_i$ 、${\beta }_i$ 、${\gamma }_i$ 为煤耗系数；$P_{i,t}$ 为机组i在t时段的出力；$C_{i,t}$ 为机组i在t时段的启动费用。

UC问题的约束条件如下：

1) 出力的约束条件

$u_{i,t}{\underset{\_}{P}}_i\le P_{i,t}\le u_{i,t}{\overline{P}}_i,\forall i,t$ (2)

其中${\underset{\_}{P}}_i$ ，${\overline{P}}_i$ 为机组i出力的上下限。

2) 功率平衡的约束条件

${\displaystyle \sum _{i=1}^N{P}_{i,t}}-P_{\text{D},t}=0\text{, }\forall t$ (3)

其中$P_{\text{D},t}$ 为时段t系统的总负荷。

3) 旋转备用的约束条件

${\displaystyle \sum _{i=1}^N{u}_{i,t}{\overline{P}}_i}\ge P_{\text{D},t}+R_t,\forall t$ (4)

其中$R_t$ 为时段t系统的旋转备用。

4) 最小启停时间的约束条件

$\{\begin{array}{l}{\displaystyle \sum _{s=t-{\underset{\_}{T}}_{\text{on},i}+1}^t{v}_{i,s}-u_{i,t}}\le 0\text{, }\forall i,t\in \left[{\underset{\_}{T}}_{\text{on},i},T\right]\\ {\displaystyle \sum _{s=t-{\underset{\_}{T}}_{\text{off},i}+1}^t{w}_{i,s}+u_{i,t}}\le 1\text{, }\forall i,t\in \left[{\underset{\_}{T}}_{\text{off},i},T\right]\\ v_{i,t}-w_{i,t}=u_{i,t}-u_{i.t-1}\text{, }\forall i,t\\ 0\le v_{i,t}\le 1\text{, 0}\le w_{i,t}\le 1\text{, }\forall i,t\end{array}$ (5)

其中$v_{i,t}$ 为机组i在t时段的启动状态，如果机组i在t时段启动，则$v_{i,t}=1$ ，否则$v_{i,t}=0$ ；$w_{i,t}$ 为机组i在t时段的停机状态，如果机组i在t时段关闭，则$w_{i,t}=1$ ，否则$w_{i,t}=0$ ；${\underset{\_}{T}}_{\text{on},i}$ 为机组i的最小运行时间；${\underset{\_}{T}}_{\text{off},i}$ 为机组i的最小停机时间。

5) 启动费用的约束条件

$\{\begin{array}{l}{C}_{i,t}\ge C_{\text{hot},i}{v}_{i,t}\text{, }\forall i,t\\ C_{i,t}\ge C_{\text{cold},i}\left[v_{i,t}-{\displaystyle \sum _{s=t-{\underset{\_}{T}}_{\text{off},i}-T_{\text{cold},i}}^t{w}_{i,s}}\right]\text{, }\forall i,t\end{array}$ (6)

其中$C_{\text{hot},i},C_{\text{cold},i},T_{\text{cold},i}$ 分别为机组i的热启动费用、冷启动费用和冷启动时间。

综上所述，UC问题的数学模型为如下MIQP：

$\begin{array}{l}\min F={\displaystyle \sum _{t=1}^T{\displaystyle \sum _{i=1}^N\left[f_i\left(u_{i,t},P_{i,t}\right)+C_{i,t}\right]}}\\ \text{s}\text{.t}\text{. }\left(\text{2}\right)\text{-}\left(6\right)\end{array}$ (7)

3. UC问题的线性化模型

由于前述UC问题的数学模型(7)为大规模的MIQP，用BB法直接求解计算量过大。为了减少计算量，本文基于透视割平面[10] [18]，将(7)近似为一个MILP进行求解。

根据文献[18]中的透视割平面，可将式(7)中二次函数$f_i\left(u_{i,t},P_{i,t}\right)={\alpha }_i{u}_{i,t}+{\beta }_i{P}_{i,t}+{\gamma }_i{\left(P_{i,t}\right)}^2$ 近似为线性形式$P_{i,t}\left(2{\gamma }_i{\xi }_i+{\beta }_i\right)+u_{i,t}\left({\alpha }_i-{\gamma }_i{\xi }_i\right)$ ，这里${\xi }_i$ 为$\left[{\underset{\_}{P}}_i,{\overline{P}}_i\right]$ 上的一个断点，从而可得到UC问题一个近似的MILP模型，称之为透视割平面模型(Perspective cut formulation, PCF)，其形式如下：

$\begin{array}{l}\min {\displaystyle \sum _{t=1}^T{\displaystyle \sum _{i=1}^N\left[P_{i,t}\left(2{\gamma }_i{\xi }_i+{\beta }_i\right)+u_{i,t}\left({\alpha }_i-{\gamma }_i{\xi }_i\right)+C_{i,t}\right]}}\\ \text{s}\text{.t}\text{. }\left(\text{2}\right)\text{-}\left(\text{6}\right)\end{array}$ (8)

为了改进BB方法中的上界，加快其收敛速度，本文采用文[10]中改进优先顺序的MILP形式，称之为改进优先顺序(Improved priority list, IPL)，具体如下：

$\begin{array}{l}\min {\displaystyle \sum _{t=1}^T{\displaystyle \sum _{i=1}^N{\sigma }_i{u}_{i,t}}}\\ \text{s}\text{.t}\text{. }\left(\text{4}\right)\text{,}\left(\text{5}\right)\end{array}$ (9)

其中，${\sigma }_i=f_i\left(1,{\overline{P}}_i\right)/{\overline{P}}_i$ ，称为机组的热率。

4. 算法研究

4.1. 分层固定策略

为解决传统分支定界(BB)算法中分支过多的问题，本文提出一种分层固定策略。BB算法在求解前先基于一定策略固定部分变量的取值，固定部分的变量称为上层变量，本文采用如下策略：

$u_{i,t}=\{\begin{array}{l}0,u_{i,t}\le \theta \\ 1,u_{i,t}\ge 1-\theta \end{array}$

其中$\theta$ 为取整阈值，本文$\theta$ 取值为0.001。

4.2. 节点搜索策略

BB法结构严谨，是一种确定性的全局优化方法，其本质是枚举法。BB法通过不断的分支、定界和剪支并最终获得最优解，不同的节点搜索策略将导致不同的算法执行效率。本文的搜索策略为优先处理机组启停状态最接近0.5的节点。

4.3. 松弛策略

为优化得到的初始解，现提出一种松弛策略，即松弛相邻时段机组启停状态发生改变的变量取值，即$u_{i,t}=0,u_{i,t+1}=1$ (开启机组)或$u_{i,t}=1,u_{i,t+1}=0$ (关闭机组)。在计算过程中发现，松弛关闭机组对初始解的优化相较于松弛开启机组的效果更好，并且用时更短。

4.4. BB算法

步骤1：输入问题R，设置上界$c^{\prime }=+\infty$ 。

步骤2：构建BB列表L，并将R存入其中。

步骤3：若$L=\varphi$ ，停止运算，输出最优解$x_{*}=x^{\prime }$ 和目标值$c_{*}=c^{\prime }$ ；若R无解，目标值$c_{*}=+\infty$ 。

步骤4：选择问题$Q\in L$ ，令$L=L/\left\{Q\right\}$ 。

步骤5：求解Q的连续松弛问题$Q_{\text{relax}}$ ，若$Q_{\text{relax}}$ 不可行，令$c^{″}=+\infty$ ；否则，令$x^{″}$ 为$Q_{\text{relax}}$ 的最优解，$c^{″}$ 为$Q_{\text{relax}}$ 的目标值。

步骤6：若$c^{″}\ge c^{\prime }$ ，转入步骤3。

步骤7：若$x^{″}$ 是R的可行解。令$x^{\prime }=x^{″},c^{\prime }=c^{″}$ ，转入步骤3。

步骤8：将Q划分为一系列子问题$Q_1,\cdots ,Q_k$ 。令$L=L\cup \left\{Q_1,\cdots ,Q_k\right\}$ ，转入步骤4。

4.5. BBM算法

BBM算法是在BB算法的基础上加入松弛、固定求解的一种算法。BBM算法先求解IPL模型的松弛问题，得到可行解，根据可行解的情况通过松弛、固定再求解的过程将可行解进行优化，得到原问题质量较高的次优解，具体算法步骤如下。

步骤1：求解IPL_relax，记其解为$u=\left(u_{i,t}\right)$ 。若$u_{i,t}\in \left\{0,1\right\}$ ，令$u_{i,t}^{*}=u_{i,t}$ ，转入步骤4。

步骤2：若$u_{i,t}\ge 1-\theta$ ，令$u_{i,t}=1$ ；若$u_{i,t}\le \theta$ ，令$u_{i,t}=0$ 。若对于$\forall i,t$ ，$u_{i,t}\in \left\{0,1\right\}$ ，令$u_{i,t}^{*}=u_{i,t}$ ，转入步骤4。

步骤3：将步骤2中$u_{i,t}$ 取值为0、1的变量固定在相应取值处，运用3.4节的BB算法求解IPL，记其解为$u^{*}=\left(u_{i,t}^{*}\right)$ 。

步骤4：利用$u_{i,t}^{*}$ 产生$N\times T$ 的矩阵U，其第i行的元素依次为$u_{i,1}^{*},u_{i,2}^{*},\cdots ,u_{i,T}^{*}$ 。

步骤5：将最小启停时间相同的机组归为一类，记为$i_1,i_2,\cdots ,i_n$ 。令$W=1$ 。

步骤6：松弛$i_W$ 中的开启机组和$i_1,i_2,\cdots ,i_n$ 中的关闭机组。

步骤7：将松弛之后的可行解代入PCF，求解PCF_relax，记其解为$u^{*}=\left(u_{i,t}^{*}\right)$ 。

步骤8：$W=W+1$ 。若$W\le n$ ，转入步骤6。

步骤9：若$u_{i,t}^{*}\ge 1-\theta ,u_{i,t}^{*}=1$ ；若$u_{i,t}^{*}\le \theta ,u_{i,t}^{*}=0$ 。若对于$\forall i,t$ ，$u_{i,t}^{*}\in \left\{0,1\right\}$ ，令$u^{\prime }=u_{i,t}^{*}$ ，转入步骤11。

步骤10：运用BB求解PCF，记其解为$u^{\prime }=\left(u_{i,t}\right)$ 。

步骤11：利用机组的启停状态$u^{\prime }$ 进行经济调度。

需要说明的是，BBM算法的步骤1到步骤4是为了产生一个可行解，步骤5到步骤8是将所有开启机组松弛一遍来获得更高质量的可行解。

5. 结果分析

本文机组系统数据选自文献[9]，基于Matlab R2018b，调用CPLEX 12.5求解MIQP问题和线性规划问题，CPLEX求解MIQP时精度设置为0.1%。计算机配置为Intel Core i7-10750 CPU@2.6GHz 8GB DDR4。

表1给出所提BBM算法的运算结果。由表1可知，对于所有系统，所提算法均在4秒内运行完毕，说明所提算法收敛速度快。这主要得益于两个方面的原因：第一个方面的原因是所给UC问题的数学模型是一种比较紧的描述，逼近问题的凸包；第二个方面的原因是，本文所提的启发式方法有效，加快了算法的收敛速度。

Table 1. Results of the proposed algorithm BBM

表1. 本文所提BBM算法的计算结果

表2给出所提方法与其他7种方法的计算结果比较，表中粗体部分表示对应各个机组系统的最小发电总费用。由表2可知，对于大部分机组系统，所提BBM方法获得的发电总费用最小，说明所提方法有效。需要说明的是，文[15]和[20]中的方法为MILP方法，均只给出部分机组系统的计算结果。

Table 2. Comparison of the different methods

表2. 不同方法的计算结果比较

表3给出与直接求解UC问题MIQP模型的计算结果比较。表中相对误差为：运算结果与直接求解MIQP模型的运行结果的差再除以运算结果。从发电总费用上看，对于10机组、20机组和100机组系统，BBM法所求的计算结果稍逊于MIQP方法；对于40机组、60机组和80机组系统，BBM法所求的计算结果略优于MIQP方法。但对于所有机组系统，两种方法的计算结果相当，差别不大。从运行时间上看，对于所有系统，所提BBM方法的计算时间占优，特别是大规模的60和100机组系统。综合发电总费用和计算时间可见，所提方法具有良好的收敛性，这主要得益于UC问题数学模型的紧性和所提启发式方法的有效性。

Table 3. Comparison of two algorithms

表3. 两种计算方法的计算结果比较

6. 结论

本文在传统分支定界方法的基础上，提出了一些改进策略，提高了UC问题的求解效率。首先，依据机组的热率构建改进的优先顺序模型，优先开启热率较高的机组，获得UC问题质量较高的可行解，改善了BB法的上界。然后，利用透视割平面，将MIQP问题转化为MILP问题，进一步减小了问题求解的复杂度。为加速BB方法的收敛速度，对上层变量进行固定，并优先搜索机组启停状态最接近0.5的节点。数值结果表明，所提方法能在合理的计算时间内获得UC问题高质量的次优解，具有良好的收敛性，适合求解大规模UC问题。

基金项目

2021年度河南工业大学自科创新基金支持计划项目(2020ZKCJ08)。

参考文献