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.
高倩, 杨知方, 李文沅. 电力系统混合整数线性规划问题的运筹决策关键技术综述与展望[J]. 电工技术学报, 2024, 39(11): 3291-3307.
Gao Qian, Yang Zhifang, Li Wenyuan. Prospect on Operations Research for Mixed-Integer Linear Programming Problems in Power Systems. Transactions of China Electrotechnical Society, 2024, 39(11): 3291-3307.
[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]. 电工技术学报, 2023, 38(24): 6727-6743. Wang Yi, Yang Zhifang, Yu Juan, et al.A unified optimal placement method for multiple types of devices in distribution networks considering reliability demand[J]. Transactions of China Electrotechnical Society, 2023, 38(24): 6727-6743. [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, Chetelat D, Ferroni N, et al.Exact combinatorial optimization with graph convolutional neural networks[C]//Advances in Neural Information Processing Systems: Curran Associates, Inc., Vancouver, Canada, 2019: 15580-15592. [47] Nair V, Bartunov S, Gimeno F, et al. Solving mixed integer programs using neural networks[EB/OL]. arXiv, 2020: 2012.13349. https://arxiv.org/abs/2012.13349.pdf. [48] Gu Xiaoyi, Dey S, Xavier A, et al. Exploiting instance and variable similarity to improve learning-enhanced branching[EB/OL]. arXiv, 2022: 2208.10028. https://arxiv.org/abs/2208.10028.pdf. [49] Sabharwal A, Samulowitz H, Reddy C.Guiding combinatorial optimization with UCT[C]//International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Berlin, Germany, 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, China, 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]//International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, Berlin, Germany, 2010: 186-202. [59] Tang Yunhao, Agrawal S, Faenza Y. Reinforcement learning for integer programming: learning to cut[EB/OL]. arXiv, 2019: 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]. arXiv, 2021: 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]// International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Thessaloniki, Greece, 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]//International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Los Angeles, CA, USA, 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] Fischetti M, Monaci M.Backdoor branching[C]// International Conference on Integer Programming and Combinatorial Optimization, Berlin, Heidelberg, 2011: 183-191. [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] World Wind Energy Association. Wind power capacity worldwide reaches 597 GW, 50.1 GW added in 2018[EB/OL]. [2019-07-04]. http://wwindea.org/blog/2019/02/25/wind-power-capacity-worldwide-reaches-600-gw-539-gw-added-in-2018.
2024, Vol. 39 
