从NP-Hard到多项式时间算法的大规模机组组合近似线性规划:双重凸包模型  

An Approximate Linear Program From an NP-hard to a Polynomial Time Complexity for a Large-scale Unit Commitment:Dual Convex Hull Model

作　　者：曲明 丁涛[1] 李立 迟方德 贺元康 陈天恩 王凤宇 QU Ming;DING Tao;LI Li;CHI Fangde;HE Yuankang;CHEN Tian’en;WANG Fengyu(State Key Lab of Electrical Insulation and Power Equipment(School of Electrical Engineering,Xi’an Jiaotong University),Xi’an 710049,Shaanxi Province,China;State Grid Shaanxi Electric Power Company,Xi’an 710048,Shaanxi Province,China;Northwest Branch of State Grid Corporation of China,Xi’an 710048,Shaanxi Province,China;Electrical and Computer Engineering Department,New Mexico State University,Las Cruces 88003,NM,USA)

机构地区：[1]电力设备电气绝缘国家重点实验室(西安交通大学电气工程学院),陕西省西安市710049 [2]国网陕西省电力公司,陕西省西安市710048 [3]国家电网公司西北分部,陕西省西安市710048 [4]新墨西哥州立大学电气与计算机工程,美国新墨西哥州拉斯克鲁塞斯88003

出　　处：《中国电机工程学报》2022年第9期3261-3275,共15页Proceedings of the CSEE

基　　金：国家自然科学基金项目(51977166);陕西电力公司新能源消纳科技专项项目(SGSN0000TKJS2001711);陕西省重点研发计划国际合作项目(2020KW-022)。

摘　　要：机组组合优化是电力系统经济运行的核心模型之一,通常以成本最小为目标函数,满足电力系统运行的物理约束和安全约束。从数学模型上讲,机组组合为混合整数规划问题,其本质是一个NP-hard问题。随着系统规模的增加,整数变量随之增加,其计算复杂度也会急剧增加。为了克服“维数灾”的挑战,该文基于单机组凸包理论将单机组凸包扩展到多机系统,建立考虑安全约束的大规模机组组合问题的凸包模型,即双重凸包模型。进而,设计双重凸包嵌入多机组机组组合的策略和多项式时间内的可行解构造方法,解决了机组对不同凸包的适应性问题和多机组凸包松弛性引起的最优解非0-1解问题。双重凸包模型将混合整数规划近似转化为线性规划,无需任何整数变量,实现机组组合求解复杂度从NP-hard到多项式时间的重要突破,适用于大规模电力系统机组组合模型。多个省级实际电力系统的仿真证明所提方法计算效率比纯混合整数规划提高1~2个数量级。Unit commitment is one of the most important models for power system economics and operations.It usually takes the minimum cost as the objective function to meet the physical and security constraints of the power system operation.Mathematically,unit commitment is mixed-integer programming,which is essentially an NP-hard problem.As the scale of the system increases,the number of integer variables increases,and its computational complexity will also increase dramatically.In order to address the challenge of“the curse of dimensionality”,this paper,based on the convex hull theory of single-unit,extended the convex hull of single-unit to multi-unit systems and established a convex hull model for large-scale unit commitment problems considering security constraints.Meanwhile,the strategy of dual convex hull embedded in multi-units commitment and the method of constructing a feasible solution were designed to solve the adaptability problem of units to convex hull and the non-0-1 solution problem of the optimal solution caused by the relaxation of the multi-units convex hull.Furthermore,two convex hulls were applied to multi-unit security-constrained unit commitment where the mixed-integer programming model was approximately transformed into linear programming,and integers were omitted.This idea has achieved an important breakthrough in the computational complexity from the NP-hard to the polynomial time,suitable for large-scale power system unit commitment models.Finally,simulation results of several provincial power systems show that the computational efficiency of the proposed method is 1~2 orders of magnitude higher than that of pure mixed-integer programming.

关 键 词：机组组合 凸包 混合整数规划 动态规划 

分 类 号：TM73[电气工程—电力系统及自动化]