电力系统混合整数线性规划问题的运筹决策关键技术综述与展望

doi:10.19595/j.cnki.1000-6753.tces.230478

摘要
图/表
参考文献
相关文章 (12)

全文: PDF (859 KB)
输出: BibTeX | EndNote (RIS)

摘要

机组组合、检修计划、拓扑运行优化、电力系统规划等电力系统混合整数线性规划（Mixed-Integer Linear Programming, MILP）问题旨在实现电力资源的最佳配置,应用广泛,其精准性与高效性直接影响了电力系统运行的安全性与经济性。随着“双碳”目标的提出,新型电力系统MILP问题模型复杂度更高、计算效率要求更严格,对当前运筹决策技术提出了更严峻的挑战。然而,现有依赖于国外进口求解器的电力系统运筹决策技术面临“组合爆炸”,且求解器依赖进口面临“卡脖子”困境,亟需实现技术突破。为此,本文系统梳理了电力系统MILP问题的运筹决策技术,以及近年来通用MILP问题的最新进展,并展望了电力系统MILP问题运筹决策关键技术未来的研究方向,旨在为我国相关研究工作提供参考和思路。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	高倩
	杨知方
	李文沅

关键词 ：电力系统优化, 混合整数线性规划, 运筹决策, MILP求解器

Abstract：

The mixed-integer linear programming (MILP) problem is formulated to find the optimal decision in a discrete search decision space, which is wildly used in power systems, such as the unit commitment, maintenance scheduling, optimal transmission switching, power system planning, etc. MILP aims to achieve the best allocation of resources, whose accuracy and efficiency directly affect the security and economy of power systems. In a MILP model, both discrete and continuous decision variables are considered, and the physical constraints in power systems are linearly formulated because of the robustness and the convergence.
Under the non-deterministic polynomial-time hardness, the number of feasible solutions to MILP is exponential to the scale of discrete decision variables, and cannot obtain the optimal solution by enumeration within the polynomial-time. Many methods and algorithms are proposed for MILP in power systems. Recently, the MILP solvers with the branch-and-bound (B&B) algorithm as the core is developing rapidly, and bring a considerable improvement to the solution efficiency, stability, and generality. Commercial MILP solvers, such as CPLEX, GUROBI, etc., have been the dominated technology for MILP in power industries.
However, MILP solvers still suffers from “combinatorial explosion” for large-scale MILP in power systems, and the independent intellectual property rights are restricted. Compared with commercial solvers, the open-source or the domestic MILP solvers has a gap in the solution efficiency. It is essential to develop a technological breakthrough for MILP in power systems. Therefore, this paper reviews the operation research in power systems and the latest developments in general MILP, and provides a future prospect on this topic, in order to offer a reference.
First, this paper suggests several typical problems in power systems, including the unit commitment, maintenance scheduling, optimal transmission switching, power system planning, etc., that can be formulated with a general MILP form. Second, this paper introduces a unified framework to solve the MILP model, while existing research is divided into different modules in the framework, i.e., the solution process: (1) external model processing, including the processing of variables, constraints, and formulations; (2) presolve and cutting planes; (3) the branch-and-bound algorithm, including the variable selection strategy, the node selection strategy, and the heuristic; 4) parameter tuning, including the solution time prediction. Third, this paper summaries that the bottleneck of operation research in power systems is: (1) the wildly-studied external model processing methods cannot balance the optimality guarantee and the solution efficiency; (2) the internal algorithms are designed for general MILP instead of specific for MILP in power systems. Therefore, this paper presents the prospect for the future research of operations research in power systems that customized strategies should be developed based on both the physical feature of power systems and the mathematical information of MILP solvers. This idea is composed of three steps: (1) to build the physical feature of power systems; (2) to dig out the internal information during the solution process; (3) to embed the customized strategies into the solution process.
In conclusion, this paper aims to draw the academic attention to the innovative research idea for MILP in power systems, and to provide a reference for related work in China. Although this paper does not consider the nonlinear nature of operation research in power systems, the main content should provide an inspiration for the general combinational problem.

Key words： Power system optimization mixed-integer linear programming operations research MILP solver

收稿日期: 2023-04-17

PACS:

TM73

基金资助:

国家重点研发计划（2021YFE0191000）和国家自然科学基金（52177072）资助项目

通讯作者: 杨知方男,1992年生,博士,教授,博士生导师,研究方向为电力系统优化、电力市场。E-mail：zfyang@cqu.edu.cn

作者简介: 高倩女,1997年生,博士研究生,研究方向为电力系统优化、混合整数线性规划、机器学习。E-mail：gaoqianmail@cqu.edu.cn

引用本文:

高倩, 杨知方, 李文沅. 电力系统混合整数线性规划问题的运筹决策关键技术综述与展望[J]. 电工技术学报, 0, (): 230478-230478. Gao Qian, Yang Zhifang, Li Wenyuan. Prospect on Operations Research for Mixed-Integer Linear Programming Problems in Power Systems. Transactions of China Electrotechnical Society, 0, (): 230478-230478.

链接本文:

https://dgjsxb.ces-transaction.com/CN/10.19595/j.cnki.1000-6753.tces.230478 https://dgjsxb.ces-transaction.com/CN/Y0/V/I/230478

[1] 李文沅. 电力系统安全经济运行: 模型与方法[M]. 重庆: 重庆大学出版社, 1989.
[2] Quarm E, Madani R.Scalable security-constrained unit commitment under uncertainty via cone programming relaxation[J]. IEEE Transactions on Power Systems, 2021, 36(5): 4733-4744.
[3] 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.
[4] Cain M, O’Neill R, Castillo A. History of Optimal Power Flow and Formulations[J]. Federal Energy Regulatory Commission, 2012, 1: 1-36.
[5] Mittelmann H. Decison Tree for Optimization Software[EB/OL]. [2023-04-13]. http://plato.asu.edu/bench.html.
[6] 吴熙, 陆瑶, 蔡晖, 等. 计及风电不确定性的含线间潮流控制器的电力系统经济调度[J]. 电工技术学报, 2023, 38(3): 781-792.
Wu Xi, Lu Yao, Cai Hui, et al.Economic dispatching of power system with interline power flow controller considering wind power uncertainty[J]. Transactions of China Electrotechnical Society, 2023, 38(3): 781-792.
[7] 徐玉琴, 方楠. 基于分段线性化与改进二阶锥松弛的电-气互联系统多目标优化调度[J]. 电工技术学报, 2022, 37(11): 2800-2812.
Xu Yuqin, Fang Nan.Multi objective optimal scheduling of integrated electricity-gas system based on piecewise linearization and improved second order cone relaxation[J]. Transactions of China Electrotechnical Society, 2022, 37(11): 2800-2812.
[8] 吴孟雪, 房方. 计及风光不确定性的电-热-氢综合能源系统分布鲁棒优化[J]. 电工技术学报, 2023, 38(13): 3473-3485.
Wu Mengxue, Fang Fang.Distributionally robust optimization of electricity-heat-hydrogen integrated energy system with wind and solar uncertainties[J]. Transactions of China Electrotechnical Society, 2023, 38(13): 3473-3485.
[9] 周博, 艾小猛, 方家琨, 等. 计及超分辨率风电出力不确定性的连续时间鲁棒机组组合[J]. 电工技术学报, 2021, 36(7): 1456-1467.
Zhou Bo, Ai Xiaomeng, Fang Jiakun, et al.Continuous-time modeling based robust unit commitment considering beyond-the-resolution wind power uncertainty[J]. Transactions of China Electrotechnical Society, 2021, 36(7): 1456-1467.
[10] 顾雪平, 白岩松, 李少岩, 等. 考虑风电不确定性的电力系统恢复全过程两阶段鲁棒优化方法[J]. 电工技术学报, 2022, 37(21): 5462-5477.
Gu Xueping, Bai Yansong, Li Shaoyan, et al.Two stage robust optimization method for the whole-process power system restoration considering wind power uncertainty[J]. Transactions of China Electrotechnical Society, 2022, 37(21): 5462-5477.
[11] 高晨, 赵勇, 汪德良, 等. 海上风电机组电气设备状态检修技术研究现状与展望[J]. 电工技术学报, 2022, 37(增刊1): 30-42.
Gao Chen, Zhao Yong, Wang Deliang, et al.Research status and prospect of condition based maintenance technology for offshore wind turbine electrical equipment[J]. Transactions of China Electrotechnical Society, 2022, 37(S1): 30-42.
[12] 杨知方, 钟海旺, 夏清, 等. 输电网结构优化问题研究综述和展望[J]. 中国电机工程学报, 2016, 36(2): 426-434.
Yang Zhifang, Zhong Haiwang, Xia Qing, et al.Review and prospect of transmission topology optimization[J]. Proceedings of the CSEE, 2016, 36(2): 426-434.
[13] 赵伟, 熊正勇, 潘艳, 等. 计及碳排放流的电力系统低碳规划[J]. 电力系统自动化, 2023, 47(9): 23-33.
Zhao Wei, Xiong Zhengyong, Pan Yan, et al.Low-carbon planning of power system considering carbon emission flow[J]. Automation of Electric Power Systems, 2023, 47(9): 23-33.
[14] Meus J, Poncelet K, Delarue E.Applicability of a clustered unit commitment model in power system modeling[J]. IEEE Transactions on Power Systems, 2018, 33(2): 2195-2204.
[15] Du Ershun, Zhang Ning, Kang Chongqing, et al.A high-efficiency network-constrained clustered unit commitment model for power system planning studies[J]. IEEE Transactions on Power Systems, 2019, 34(4): 2498-2508.
[16] Yin Yue, He Chuan, Liu Tianqi, et al.Risk-averse stochastic midterm scheduling of thermal-hydro-wind system: a network-constrained clustered unit commitment approach[J]. IEEE Transactions on Sustainable Energy, 2022, 13(3): 1293-1304.
[17] Pineda S, Fernández-Blanco R, Morales J M.Time-adaptive unit commitment[J]. IEEE Transactions on Power Systems, 2019, 34(5): 3869-3878.
[18] Zhang Menghan, Yang Zhifang, Lin Wei, et al.Enhancing economics of power systems through fast unit commitment with high time resolution[J]. Applied Energy, 2021, 281: 116051.
[19] 汪洋, 夏清, 康重庆. 机组组合算法中起作用整数变量的辨识方法[J]. 中国电机工程学报, 2010, 30(13): 46-52.
Wang Yang, Xia Qing, Kang Chongqing.Identification of the active integer variables in security constrained unit commitment[J]. Proceedings of the CESS, 2010, 30(13): 46-52.
[20] Xavier Álinson S, Feng Qiu, Shabbir A.Learning to solve large-scale security-constrained unit commitment problems[J]. INFORMS Journal on Computing, 2020, 33(2): 739-756.
[21] Ardakani A J, Bouffard F.Identification of umbrella constraints in DC-based security-constrained optimal power flow[J]. IEEE Transactions on Power Systems, 2013, 28(4): 3924-3934.
[22] Ardakani A J, Bouffard F.Acceleration of umbrella constraint discovery in generation scheduling problems[J]. IEEE Transactions on Power Systems, 2015, 30(4): 2100-2109.
[23] Thompson G L, Tonge F M, Zionts S.Techniques for removing nonbinding constraints and extraneous variables from linear programming problems[J]. Management Science, 1966, 12(7): 588-608.
[24] Yang Yafei, Guan Xiaohong, Zhai Qiaozhu.Fast grid security assessment with N - k contingencies[J]. IEEE Transactions on Power Systems, 2017, 32(3): 2193-2203.
[25] 袁泉, 孙宇军, 张蔷, 等. 考虑安全约束耦合辨识的日前发电计划求解[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.
[26] Brearley A L, Mitra G, Williams H P.Analysis of mathematical programming problems prior to applying the simplex algorithm[J]. Mathematical Programming, 1975, 8(1): 54-83.
[27] Capitanescu F, Glavic M, Ernst D, et al.Contingency filtering techniques for preventive security-constrained optimal power flow[J]. IEEE Transactions on Power Systems, 2007, 22(4): 1690-1697.
[28] Capitanescu F, Wehenkel L.A new iterative approach to the corrective security-constrained optimal power flow problem[J]. IEEE Transactions on Power Systems, 2008, 23(4): 1533-1541.
[29] Santos Xavier Á, Qiu Feng, Wang Fengyu, et al.Transmission constraint filtering in large-scale security-constrained unit commitment[J]. IEEE Transactions on Power Systems, 2019, 34(3): 2457-2460.
[30] Pineda S, Morales J M, Jiménez-Cordero A.Data-driven screening of network constraints for unit commitment[J]. IEEE Transactions on Power Systems, 2020, 35(5): 3695-3705.
[31] Zhang Shubo, Ye Hongxing, Wang Fengyu, et al.Data-aided offline and online screening for security constraint[J]. IEEE Transactions on Power Systems, 2021, 36(3): 2614-2622.
[32] Mohammadi F, Sahraei-Ardakani M, Trakas D N, et al.Machine learning assisted stochastic unit commitment during hurricanes with predictable line outages[J]. IEEE Transactions on Power Systems, 2021, 36(6): 5131-5142.
[33] Holzer J T, Chen Yonghong, Wu Zhongyu, et al. Fast simultaneous feasibility test for security constrained unit commitment[J]. IEEE Transactions on Power Systems, 2023, PP(99): 1-10.
[34] Tejada-Arango D A, Lumbreras S, Sánchez-Martín P, et al. Which unit-commitment formulation is best? A comparison framework[J]. IEEE Transactions on Power Systems, 2020, 35(4): 2926-2936.
[35] Knueven B, Ostrowski J, Watson J.On mixed-integer programming formulations for the unit commitment problem[J]. Informs Journal on Computing, 2020, 32(4): 857-876.
[36] Ma Ziming, Zhong Haiwang, Xia Qing, et al.A unit commitment algorithm with relaxation-based neighborhood search and improved relaxation inducement[J]. IEEE Transactions on Power Systems, 2020, 35(5): 3800-3809.
[37] Yu Yanan, Guan Yongpei, Chen Yonghong.An extended integral unit commitment formulation and an iterative algorithm for convex hull pricing[J]. IEEE Transactions on Power Systems, 2020, 35(6): 4335-4346.
[38] Schiro D A, Zheng Tongxin, Zhao Feng, et al.Convex hull pricing in electricity markets: formulation, analysis, and implementation challenges[J]. IEEE Transactions on Power Systems, 2016, 31(5): 4068-4075.
[39] Álvarez C, Mancilla-David F, Escalona P, et al.A bienstock-zuckerberg-based algorithm for solving a network-flow formulation of the convex hull pricing problem[J]. IEEE Transactions on Power Systems, 2020, 35(3): 2108-2119.
[40] Yan Bing, Luh P B, Zheng Tongxin, et al.A systematic formulation tightening approach for unit commitment problems[J]. IEEE Transactions on Power Systems, 2020, 35(1): 782-794.
[41] Achterberg T, Bixby R E, Gu Zonghao, et al.Presolve reductions in mixed integer programming[J]. INFORMS Journal on Computing, 2020, 32(2): 473-506.
[42] CPLEX. What are cuts?- IBM Documentation[EB/OL]. [2023-04-13]. https://www.ibm.com/docs/en/icos/22.1.0?topic=cuts-what-are.
[43] Yang Yu, Boland N, Dilkina B, et al.Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems[J]. European Journal of Operational Research, 2022, 301(3): 828-840.
[44] Lodi A, Zarpellon G.On learning and branching: a survey[J]. TOP, 2017, 25(2): 207-236.
[45] Khalil E B, Le Bodic P, Song Le, et al.Learning to branch in mixed integer programming[C]//Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, 2016: 724-731.
[46] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks[EB/OL].2019: arXiv: 1906.01629. https://arxiv.org/abs/1906.01629.pdf
[47] Nair V, Bartunov S, Gimeno F, et al.Solving Mixed Integer Programs Using Neural Networks[M]. arXiv, 2021.
[48] Gu Xiaoyi, Dey S, Xavier A, et al.Exploiting Instance and Variable Similarity to Improve Learning-Enhanced Branching[M]. arXiv, 2022.
[49] Sabharwal A, Samulowitz H, Reddy C.Guiding combinatorial optimization with UCT[C]//Beldiceanu N, Jussien N, Pinson É. International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming. Berlin, Heidelberg: Springer, 2012: 356-361.
[50] Berthold T, Lodi A, Salvagnin D.Ten years of feasibility pump, and counting[J]. EURO Journal on Computational Optimization, 2019, 7(1): 1-14.
[51] Danna E, Rothberg E, Le Pape C.Exploring relaxation induced neighborhoods to improve MIP solutions[J]. Mathematical Programming, 2005, 102(1): 71-90.
[52] Rothberg E.An evolutionary algorithm for polishing mixed integer programming solutions[J]. INFORMS Journal on Computing, 2007, 19(4): 534-541.
[53] Pferschy U, Staněk R.Generating subtour elimination constraints for the TSP from pure integer solutions[J]. Central European Journal of Operations Research, 2017, 25(1): 231-260.
[54] Wang Kangping, Huang Lan, Zhou Chunguang, et al.Particle swarm optimization for traveling salesman problem[C]//Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.03EX693), Xi'an, 2004: 1583-1585.
[55] Gao Qian, Yang Zhifang, Yin Wotao, et al.Internally induced branch-and-cut acceleration for unit commitment based on improvement of upper bound[J]. IEEE Transactions on Power Systems, 2022, 37(3): 2455-2458.
[56] Koc U, Mehrotra S.Generation of feasible integer solutions on a massively parallel computer using the feasibility pump[J]. Operations Research Letters, 2017, 45(6): 652-658.
[57] Koch T, Ralphs T, Shinano Y.Could we use a million cores to solve an integer program?[J]. Mathematical Methods of Operations Research, 2012, 76(1): 67-93.
[58] Hutter F, Hoos H H, Leyton-Brown K.Automated configuration of mixed integer programming solvers[C]//Lodi A, Milano M, Toth P. International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming. Berlin, Heidelberg: Springer, 2010: 186-202.
[59] Tang Yunhao, Agrawal S, Faenza Y. Reinforcement learning for integer programming: learning to cut[EB/OL].2019: arXiv: 1906.04859. https://arxiv.org/abs/1906.04859.pdf
[60] Chmiela A, Khalil E B, Gleixner A, et al. Learning to schedule heuristics in branch-and-bound[EB/OL].2021: arXiv: 2103.10294. https://arxiv.org/abs/2103.10294.pdf
[61] de Souza M. Automatic design of heuristic algorithms for binary optimization problems[C]//Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, Montreal, Canada, 2021: 4881-4882.
[62] Fischetti M, Lodi A, Zarpellon G.Learning MILP resolution outcomes before reaching time-limit[C]//Rousseau LM, Stergiou K. International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Cham: Springer, 2019: 275-291.
[63] Gregor H, Daniel A, Pierre L B, et al.Estimating the size of branch-and-bound trees[J]. INFORMS Journal on Computing, 2021, 34(2): 934-952.
[64] Berthold T, Hendel G, Koch T.From feasibility to improvement to proof: three phases of solving mixed-integer programs[J]. Optimization Methods and Software, 2018, 33(3): 499-517.
[65] Safdarian F, Mohammadi A, Kargarian A.Temporal decomposition for security-constrained unit commitment[J]. IEEE Transactions on Power Systems, 2020, 35(3): 1834-1845.
[66] Feizollahi M J, Costley M, Ahmed S, et al.Large-scale decentralized unit commitment[J]. International Journal of Electrical Power & Energy Systems, 2015, 73: 97-106.
[67] Chen Yonghong, Pan Feng, Qiu Feng, et al.Security-constrained unit commitment for electricity market: modeling, solution methods, and future challenges[J]. IEEE Transactions on Power Systems, 2023, 38(5): 4668-4681.
[68] Ding Jianya, Zhang Chao, Shen Lei, et al.Accelerating primal solution findings for mixed integer programs based on solution prediction[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2020, 34(2): 1452-1459.
[69] Berthold T, Hendel G, Salvagnin D.Transferring information across restarts in MIP[C]//Schaus P. International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Cham: Springer, 2022: 24-33.
[70] Anderson D, Hendel G, Le Bodic P, et al.Clairvoyant restarts in branch-and-bound search using online tree-size estimation[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019, 33(1): 1427-1434.
[71] Günlük O, Woeginger G.Integer Programming and Combinatoral Optimization: 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings[M]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.
[72] Claudio C, Andrea L, Andrea T.Cutting planes from the branch-and-bound tree: challenges and opportunities[J]. INFORMS Journal on Computing, 2022, 35(1): 2-4.
[73] Gao Qian, Yang Zhifang, Li Wenyuan, et al.Online learning of stable integer variables in unit commitment using internal information[J]. IEEE Transactions on Power Systems, 2023, 38(3): 2947-2950.
[74] Bengio Y, Lodi A, Prouvost A.Machine learning for combinatorial optimization: a methodological tour d’horizon[J]. European Journal of Operational Research, 2021, 290(2): 405-421.
[75] Achterberg T.What’s New - Gurobi 10.0[EB/OL]//Gurobi Optimization.[2023-04-03]. https://www.gurobi.com/whats-new-gurobi-10-0/.