求解机组组合问题的两种MILP方法比较

[摘 要]利用机组的煤耗成本，建立机组组合（unit commitment， UC）问题不考虑发电出力的混合整数线性规划（mixed integer linear programming， MILP）模型。和UC问题的传统模型相比，该模型不包括机组出力变量及相应约束，模型规模和求解难度都大大减小。将所建MILP模型和基于透视割平面的MILP模型用于求解168时段1000机组等多个系统，结果表明，无论是发电费用还是计算时间，所建模型都具有一定的优越性。

[关键词]煤耗成本；机组组合问题；混合整数线性规划；透视割平面

中图分类号：TM71 文献标识码：A 文章编号：1009-914X（2015）48-0332-02

引言

机组组合（unit commitment， UC）问题是电力系统一个重要的调度规划问题，多年来一直受到科技工作者的广泛关注和研究[1]。

对于UC问题的研究主要集中于两个方面，一个方面是关于其数学模型的研究[2-4]，另一个方面是关于求解方法的研究[5-7]。文献[2]基于凸规划理论，建立了UC问题的半定规划模型，文献[3]利用锥规划建立了UC问题的二阶锥规划模型，文献[4]基于透视割平面（perspective cut， PC）建立UC问题一个紧的混合整数线性规划（mixed integer linear programming， MILP）模型，同时提出了求解UC问题的MILP方法。文献[5]提出求解UC问题的拓广优先顺序法，文献[6]提出求解UC问题的增广拉格朗日松弛法，文献[7]提出求解UC问题的粒子群算法。

MILP法是目前求解UC问题的主流算法，已在实际调度中得到了广泛的应用。然而，对于大规模UC问题，通常的MILP模型规模很大，即使应用目前先进的MILP求解器（如CPLEX），也会存在计算量大的不足。为此，利用机组的煤耗成本，建立UC问题一个不考虑机组出力的MILP模型。该模型和UC问题通常的MILP模型相比，由于其不含机组出力变量和相应的约束，从而其求解规模和难度都大大减少。最后，将所提MILP方法和基于PC的MILP方法用于求解1000机组168时段等多个系统，结果表明，无论是发电费用还是计算时间，所提MILP方法都优于基于PC的MILP方法。

1 UC问题的数学模型

UC问题要实现的目标为：

（1）

（2）

UC问题的限制条件为：

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

前面式中各量的意义分别为：T为总的调度时间（小时）；N为机组总数（台）；为机组i的状态变量，为0-1整数变量；为机组参数；为机组出力；为启动费用；分别为热/冷启动费用；分别为开机变量和关机变量；分别为最小持续停机时间和冷启动时间；为机组出力限制；为系统负荷；为系统备用；为机组最小持续开机时间。

2 UC问题的PC模型

易知UC问题～等价于如下问题：

（11）

利用内的点，Frangioni和Gentile在文献[4]中提出如下的PC

（12）

进而得到UC问题如下的MILP模型

（13）

这里先利用MILP获得UC问题的机组启停状态，进而利用UC问题～获得发电总费用，这样的算法简称为PC。

3 UC问题的PL模型

文献[5]利用煤耗成本从小到大的顺序来运行发电机组。受文献[5]启发，这里基于煤耗成本，建立UC问题如下的MILP模型：

（14）

这里先利用MILP获得UC问题的机组启停状态，进而利用UC问题～获得发电总费用，这样的算法简称为PL。

由于不含机组出力变量及相应约束，其规模和求解难度要小于第一部分和第二部分内容里面UC问题的数学模型。

4 结果分析

下面对算法PC和PL求解UC问题的计算结果进行分析比较。基于Matlab R2011B，利用CPLEX 12.3求解PC和PL中的MILP问题和二次经济调度问题。计算机配置为：Intel Core i5-4590 3.30GHz， 32GB RAM。仿真算例的产生方法取自文献[3]，CPLEX求解MILP的精度设置为0.003，最大运行时间限制为15000秒。

表1-3分别给出10至1000机组24时段、96时段和168时段的计算结果，表中黑体部分表示更少的计算时间和更小的发电总费用。

从表1可以看出，除了200机组和1000机组系统外，算法PL比PC获得了更优的发电费用。从计算时间来看，对于较小规模的10-100机组系统，两种方法的计算时间相差不是很大，而对于大规模的200-1000机组系统，PL算法运行的时间要显著少于PC的运行时间，综合考虑发电费用和计算时间，算法PL在一定程度上优于PC。

相对于表1，表2给出更大规模系统的运行结果。由表2可知，对于所有系统，无论是计算时间还是发电费用，算法PL的运行结果都要优于PC的运行结果，尤其是对于大规模的机组系统，PL的运行时间要远远少于PC的运行时间，这些都说明了PL的优越性。

表3给出大规模的168时段系统两种算法的运行结果。表3显示，除了10机组系统外，对于其他所有系统，PL所得的发电费用都优于PC获得的发电费用，至于计算时间，PL则具有明显的优势，尤其是对于大规模的100-1000系统，表3说明算法PL的计算结果要优于PC的计算结果。

综合前述结果比较及分析，无论是对于计算时间还是发电费用，算法PL的运行结果都要优于PC的运行结果，说明算法PL在求解UC问题时具有一定的优势。

参考文献

[1] Padhy N. Unit commitment―A bibliographical survey[J]. IEEE Trans Power Syst， 2004（19）： 1196C1205.

[2] 韦化，吴阿琴，白晓清.一种求解机组组合问题的内点半定规划方法[J].中国电机工程学报，2008，28（1）：35-40.

Wei H，Wu A Q，Bai X Q.An interior point semidefinite programming for unit commitment problems[J].Proceedings of the CSEE，2008，28（1）：35-40.

[3] 全然，韦化，简金宝.求解大规模机组组合问题的二阶锥规划方法[J].中国电机工程学报，2010，30（25）：101-106.

Quan R， Wei H， Jian J B. Solution of Large Scale Unit Commitment by Second-order Cone Programming [J].Proceedings of the CSEE，2010，30（25）：101-106.

[4] Frangionia A， Gentile C， Laclandra F. Tighter approximated MILP formulations for unit commitment problems[J]. IEEE Trans on Power Systems， 2009， 24（1）： 105-113.

[5] Senjyu T， Shimabukuro K， Uezato K， et al. A fast technique for unit commitment problem by extended priority list[J]. IEEE Trans on Power Systems， 2003， 18（2）： 882-888.

[6] Ongsakul W， Petcharaks N. Unit commitment by enhanced adaptive lagrangian relaxation[J]. IEEE Trans on Power Systems， 2004， 19（1）： 620-628.

[7] 胡家声，郭创新，曹一家.一种适合于电力系统机组组合问题的混合粒子群优化算法[J].中国电机工程学报，2004，24（4）：24-28.

[8] Hu J S， Guo C X，Cao Y J. A hybrid particle swarm optimization method for unit commitment problem[J]. Proceedings of the CSEE，2004，24（4）：24-28.