Dispatch Acceleration of Integrated Electricity and Gas System Using Branch-and-Bound Search Information
Gao Qian1, Yang Zhifang1, Li Wenyuan1, Lu Yudong2
1. State Key Laboratory of Power Transmission Equipment Technology Chongqing University Chongqing 400044 China; 2. State Grid Zhejiang Electric Power Co. Ltd Research Institute Hangzhou 310014 China
Abstract：The dispatch problem in integrated electricity and gas system is formulated as the mixed-integer linear programming (MILP) form to describe the discrete feature of resources (such as the unit statuses) and nonlinear operation rules (such as the power flow equation, the Weymouth equation, etc.). The optimal solution achieves the best allocation of resources and indicates the security and economic of the integrated electricity and gas system. However, the large-scale integer variables bring the “combinatorial explosion” challenge, even for the state-of-the-art commercial solvers. To address this problem, existing research focuses on the external algorithms, such as reformulating, reducing the scale of constraints/integer variables, etc. However, it is hard to balance the solution efficiency and the error bound guarantees in practice. Therefore, this paper proposes an internal algorithm that is highly combined with the search information in the branch-and-bound process. The distinct advantage of the proposed method is that the unique structure of integrated electricity and gas system is considered along with the abundant information during the solution process. As a result, the proposed method can achieve an acceleration with optimality guaranteed. This paper reviews the MILP formulation of the dispatch problem in integrated electricity and gas system, and focuses on the computational bottleneck, i.e., the large-scale integer variables introduced by the piecewise linearization structure of the Weymouth equation. Because most of integer variables in the piecewise linearization structure remains zero, this paper proposes to evaluate the potential effective range of integer variables in the optimal solution, based on the branch-and-bound search information. First, the proposed method collects the relaxation solutions during the initial stage of the branch-and-bound process, to build a search information dataset that implies the optimal value of the piecewise linearization structure. The relaxation solutions are easy to obtain, and they provide lower bounds to the current search tree. Therefore, the idea is that if an integer variable of the piecewise linearization always lies in a similar range across the abundant relaxation solutions, it is likely to remain the same pattern in the optimal solution. Second, the k-nearest neighbors regression algorithm is used to estimate the potential effective range of the piecewise linearization structure. Third, the proposed method builds a small-scale MILP model and solves it in parallel to produce a better solution than the main branch-and-bound process. As a result, the redundant search space in the search tree is pruned by the better solution with no accuracy loss and the optimality is guaranteed. In the case study, the effectiveness of the proposed method has been demonstrated in several aspects based on test cases of RTS-GMLC and gas system. First, for different scales of piecewise linearization structures, compared with the commercial solver, the proposed method accelerates the dispatch problem from 1.60 times to 36.90 times (11.28 times on average). The result also shows that with the improvement of the piecewise linearization scale, the computational burden suddenly increases and can be significantly mitigated by the proposed method, which provides a balance between the formulation precision and the computational efficiency. Second, for 30 test cases using different power demands, the proposed method accelerates the dispatch problem from 1.64 times to 13.52 times (4.20 times on average). It shows that the proposed method behaves well in complicated operation conditions. Third, the case study discusses some details of the proposed method, including the feasibility repair, the prediction accuracy, the upper bound convergence, the search tree scale, and time cost of each step, which provides a thoroughly analysis for the proposed method. Finally, a test case is used to demonstrate the effectiveness in the large-scale system. In conclusion, this paper proposes an acceleration algorithm for the dispatch problem in integrated electricity and gas system. The proposed method improves the solution efficiency without the loss of the optimality guarantees, which is promising in practical and provides a novel view on the optimization in power systems.
高倩, 杨知方, 李文沅, 卢毓东. 分支定界搜索信息深度引导的电-气互联系统调度决策加速求解方法[J]. 电工技术学报, 2024, 39(13): 3990-4002.
Gao Qian, Yang Zhifang, Li Wenyuan, Lu Yudong. Dispatch Acceleration of Integrated Electricity and Gas System Using Branch-and-Bound Search Information. Transactions of China Electrotechnical Society, 2024, 39(13): 3990-4002.
[1] 国家能源局关于“互联网+”智慧能源(能源互联网)示范项目评审办法的公示—国家能源局[EB/OL]. [2023-04-05]. http://www.nea.gov.cn/2016-12/09/c_ 135893950.htm. [2] Tang Yi, Zhao Yuan, Li Wenyuan, et al.Reliability evaluation of EGIES with highly nonlinear modeling of gas system components[J]. Electric Power Systems Research, 2021, 195: 107119. [3] 刘雨佳, 樊艳芳, 白雪岩, 等. 基于优化计算型区块链系统的虚拟电厂模型与调度策略[J]. 电工技术学报, 2023, 38(15): 4178-4191. Liu Yujia, Fan Yanfang, Bai Xueyan, et al.Virtual power plant model and scheduling strategy based on optimized computing block-chain system[J]. Transactions of China Electrotechnical Society, 2023, 38(15): 4178-4191. [4] 陈明昊, 孙毅, 谢志远. 基于双层深度强化学习的园区综合能源系统多时间尺度优化管理[J]. 电工技术学报, 2023, 38(7): 1864-1881. Chen Minghao, Sun Yi, Xie Zhiyuan.The multi-time-scale management optimization method for park integrated energy system based on the Bi-layer deep reinforcement learning[J]. Transactions of China Electrotechnical Society, 2023, 38(7): 1864-1881. [5] 潘超, 范宫博, 王锦鹏, 等. 灵活性资源参与的电热综合能源系统低碳优化[J]. 电工技术学报, 2023, 38(6): 1633-1647. Pan Chao, Fan Gongbo, Wang Jinpeng, et al.Low-carbon optimization of electric and heating integrated energy system with flexible resource participation[J]. Transactions of China Electrotechnical Society, 2023, 38(6): 1633-1647. [6] 刘小慧, 王小君, 张义志, 等. 考虑生物质储运模式的多区域综合能源系统协同规划[J]. 电工技术学报, 2023, 38(6): 1648-1661. Liu Xiaohui, Wang Xiaojun, Zhang Yizhi, et al.Multi-regional integrated energy system collaborative planning considering biomass storage and transportation mode[J]. Transactions of China Electrotechnical Society, 2023, 38(6): 1648-1661. [7] Yang Zhifang, Xie Kaigui, Yu Juan, et al.A general formulation of linear power flow models: basic theory and error analysis[J]. IEEE Transactions on Power Systems, 2019, 34(2): 1315-1324. [8] Correa-Posada C M. Gas network optimization: a comparison of piecewise linear models[J/OL]. Optimization online, 2014: 1-24. https://optimization-online.org/wp-content/uploads/2014/10/4580.pdf. [9] Constante-Flores G E, Conejo A J, Qiu Feng. AC network-constrained unit commitment via relaxation and decomposition[J]. IEEE Transactions on Power Systems, 2022, 37(3): 2187-2196. [10] Wu Jianghua, Luh P B, Chen Yonghong, et al.A novel optimization approach for sub-hourly unit commitment with large numbers of units and virtual transactions[J]. IEEE Transactions on Power Systems, 2022, 37(5): 3716-3725. [11] 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. [12] Mittelmann H. Decison Tree for Optimization Software[EB/OL]. [2023-04-05]. http://plato.asu.edu/ bench.html. [13] 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. [14] 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. [15] 王晗, 侯恺, 刘晓楠, 等. 基于全局灵敏度分析的电气互联系统韧性提升方法[J]. 电力系统自动化, 2023, 47(3): 59-67. Wang Han, Hou Kai, Liu Xiaonan, et al.Resilience enhancement method for electricity-gas interconnection system based on global sensitivity analysis[J]. Automation of Electric Power Systems, 2023, 47(3): 59-67. [16] Shao Chengcheng, Wang Xifan, Shahidehpour M, et al.An MILP-based optimal power flow in multicarrier energy systems[J]. IEEE Transactions on Sustainable Energy, 2017, 8(1): 239-248. [17] Wang Xu, Bie Zhaohong, Liu Fan, et al.Co-optimization planning of integrated electricity and district heating systems based on improved quadratic convex relaxation[J]. Applied Energy, 2021, 285: 116439. [18] 徐玉琴, 方楠. 基于分段线性化与改进二阶锥松弛的电-气互联系统多目标优化调度[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. [19] Li Xuan, Zhai Qiaozhu, Zhou Jingxuan, et al.A variable reduction method for large-scale unit commitment[J]. IEEE Transactions on Power Systems, 2020, 35(1): 261-272. [20] Chen Sheng, Wei Zhinong, Sun Guoqiang, et al.Optimal power and gas flow with a limited number of control actions[J]. IEEE Transactions on Smart Grid, 2018, 9(5): 5371-5380. [21] Luo Songlin, Yang Lun, Zhang Xin, et al.A fully linear-constrained optimal electricity-gas flow in an integrated energy system[C]//2018 2nd IEEE Conference on Energy Internet and Energy System Integration (EI2), Beijing, China, 2018: 1-6. [22] 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. [23] Knueven B, Ostrowski J, Watson J P.On mixed-integer programming formulations for the unit commitment problem[J]. Informs Journal on Computing, 2020: ijoc.2019.0944. [24] Ma Ziming, Zhong Haiwang, Cheng Tong, et al.Redundant and nonbinding transmission constraints identification method combining physical and economic insights of unit commitment[J]. IEEE Transactions on Power Systems, 2021, 36(4): 3487-3495. [25] 朱正春, 杨知方, 余娟, 等. 面向小样本场景的数据驱动安全约束经济调度快速计算方法[J]. 中国电机工程学报, 2022, 42(12): 4430-4440. Zhu Zhengchun, Yang Zhifang, Yu Juan, et al.A data-driven fast calculation method for security-constrained economic dispatch with small sample requirements[J]. Proceedings of the CSEE, 2022, 42(12): 4430-4440. [26] 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. [27] 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. [28] 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. [29] Gu Xiaoyi, Dey S S, Xavier S, et al. Exploiting instance and variable similarity to improve learning-enhanced branching[J]. arXiv, 2022. https://doi.org/ 10.48550/arXiv.2208.10028 [30] 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. [31] CPLEX. What are cuts?- IBM Documentation[EB/OL]. [2023-04-05]. https://www.ibm.com/docs/en/icos/22. 1.0?topic=cuts-what-are. [32] Danna E, Rothberg E, Le Pape C.Exploring relaxation induced neighborhoods to improve MIP solutions[J]. Mathematical Programming, 2005, 102(1): 71-90. [33] Berthold T, Lodi A, Salvagnin D.Ten years of feasibility pump, and counting[J]. EURO Journal on Computational Optimization, 2019, 7(1): 1-14.
2024, Vol. 39 
