一种求解机组组合问题的分支定界方法
A Branch and Bound Method for Solving Unit Commitment Problem
DOI: 10.12677/jee.2025.131002, PDF,    科研立项经费支持
作者: 张志强, 全 然：河南工业大学数学与统计学院，河南 郑州
关键词: 机组组合；分支定界；热率；透视割平面；Unit Commitment； Branch and Bound； Heat Rate； Perspective Cutting Plane
摘要: 文章提出一种求解机组组合问题的分支定界方法。利用热率和透视割平面将机组组合模型做近似线性化处理，将混合整数二次规划转化为混合整数线性规划进行求解。为提高分支定界的计算效率，进行上层变量固定并优先搜索机组启停状态最接近0.5的节点。数值结果表明，此法与直接求解混合整数二次规划的发电费用相当，但计算时间占优，适合求解大规模机组组合问题。
Abstract: This paper presents a branch and bound method for solving the unit commitment (UC) problem. The UC model is approximated to linear models by using the heat rate and perspective cutting plane, and the mixed integer quadratic programming model is transformed into mixed integer linear programming. In order to improve the computing efficiency of the branch and bound, the upper-level variables are fixed and the node closest to the value of 0.5 is searched first. Numerical results show that the generation costs by the proposed method are almost equivalent to the ones by directly solving the mixed integer quadratic programming of UC. However, the proposed method has an advantage in terms of computation time and is suitable for solving large-scale UC problems.
文章引用：张志强, 全然. 一种求解机组组合问题的分支定界方法[J]. 电气工程, 2025, 13(1): 10-17. https://doi.org/10.12677/jee.2025.131002

参考文献

[1] Padhy, N.P. (2004) Unit Commitment—A Bibliographical Survey. IEEE Transactions on Power Systems, 19, 1196-1205. [Google Scholar] [CrossRef] 
[2] Zhai, Y., Liao, X., Mu, N. and Le, J. (2019) A Two-Layer Algorithm Based on PSO for Solving Unit Commitment Problem. Soft Computing, 24, 9161-9178. [Google Scholar] [CrossRef] 
[3] Ponciroli, R., Stauff, N.E., Ramsey, J., Ganda, F. and Vilim, R.B. (2020) An Improved Genetic Algorithm Approach to the Unit Commitment/Economic Dispatch Problem. IEEE Transactions on Power Systems, 35, 4005-4013. [Google Scholar] [CrossRef] 
[4] Simopoulos, D.N., Kavatza, S.D. and Vournas, C.D. (2006) Unit Commitment by an Enhanced Simulated Annealing Algorithm. IEEE Transactions on Power Systems, 21, 68-76. [Google Scholar] [CrossRef] 
[5] Singh, A., Khamparia, A. and Al-Turjman, F. (2024) A Hybrid Evolutionary Approach for Multi-Objective Unit Commitment Problem in Power Systems. Energy Reports, 11, 2439-2449. [Google Scholar] [CrossRef] 
[6] Yin, L. and Ding, W. (2024) Deep Neural Network Accelerated-Group African Vulture Optimization Algorithm for Unit Commitment Considering Uncertain Wind Power. Applied Soft Computing, 162, Article ID: 111845. [Google Scholar] [CrossRef] 
[7] 谢国辉, 张粒子, 舒隽, 等. 基于分层分枝定界算法的机组组合[J]. 电力自动化设备, 2009, 29(12): 29-32.
[8] Cohen, A. and Yoshimura, M. (1983) A Branch-and-Bound Algorithm for Unit Commitment. IEEE Transactions on Power Apparatus and Systems, 102, 444-451. [Google Scholar] [CrossRef] 
[9] Senjyu, T., Shimabukuro, K., Uezato, K. and Funabashi, T. (2003) A Fast Technique for Unit Commitment Problem by Extended Priority List. IEEE Transactions on Power Systems, 18, 882-888. [Google Scholar] [CrossRef] 
[10] Quan, R., Jian, J. and Yang, L. (2015) An Improved Priority List and Neighborhood Search Method for Unit Commitment. International Journal of Electrical Power & Energy Systems, 67, 278-285. [Google Scholar] [CrossRef] 
[11] Hou, J., Zhai, Q., Zhou, Y. and Guan, X. (2024) A Fast Solution Method for Large-Scale Unit Commitment Based on Lagrangian Relaxation and Dynamic Programming. IEEE Transactions on Power Systems, 39, 3130-3140. [Google Scholar] [CrossRef] 
[12] Ongsakul, W. and Petcharaks, N. (2004) Unit Commitment by Enhanced Adaptive Lagrangian Relaxation. IEEE Transactions on Power Systems, 19, 620-628. [Google Scholar] [CrossRef] 
[13] Balci, H. and Valenzuela, J. (2004) Scheduling Electric Power Generators Using Particle Swam Optimization Combined with the Lagrangian Relaxation Method. International Journal of Applied Mathematics and Computer Sciences, 14, 411-421.
[14] Geoffrion, A.M. (1972) Generalized Benders Decomposition. Journal of Optimization Theory and Applications, 10, 237-260. [Google Scholar] [CrossRef] 
[15] 全然, 简金宝, 郑海艳. 基于外逼近方法的中期机组组合问题[J]. 电力系统自动化, 2009, 33(11): 24-28.
[16] Han, D., Jian, J. and Yang, L. (2014) Outer Approximation and Outer-Inner Approximation Approaches for Unit Commitment Problem. IEEE Transactions on Power Systems, 29, 505-513. [Google Scholar] [CrossRef] 
[17] Jian, J., Zhang, C., Yang, L. and Meng, K. (2019) A Hierarchical Alternating Direction Method of Multipliers for Fully Distributed Unit Commitment. International Journal of Electrical Power & Energy Systems, 108, 204-217. [Google Scholar] [CrossRef] 
[18] Frangioni, A., Gentile, C. and Lacalandra, F. (2009) Tighter Approximated MILP Formulations for Unit Commitment Problems. IEEE Transactions on Power Systems, 24, 105-113. [Google Scholar] [CrossRef] 
[19] Knueven, B., Ostrowski, J. and Watson, J. (2020) On Mixed-Integer Programming Formulations for the Unit Commitment Problem. INFORMS Journal on Computing, 32, 857-876. [Google Scholar] [CrossRef] 
[20] Carrion, M. and Arroyo, J.M. (2006) A Computationally Efficient Mixed-Integer Linear Formulation for the Thermal Unit Commitment Problem. IEEE Transactions on Power Systems, 21, 1371-1378. [Google Scholar] [CrossRef] 
[21] Land, A.H. and Doig, A.G. (1960) An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28, 497-520. [Google Scholar] [CrossRef] 
[22] Atamtürk, A. and Savelsbergh, M.W.P. (2005) Integer-Programming Software Systems. Annals of Operations Research, 140, 67-124. [Google Scholar] [CrossRef] 
[23] Nannicini, G. and Belotti, P. (2011) Rounding-based Heuristics for Nonconvex MINLPs. Mathematical Programming Computation, 4, 1-31. [Google Scholar] [CrossRef] 
[24] Dillon, T.S., Edwin, K.W., Kochs, H. and Taud, R.J. (1978) Integer Programming Approach to the Problem of Optimal Unit Commitment with Probabilistic Reserve Determination. IEEE Transactions on Power Apparatus and Systems, 97, 2154-2166. [Google Scholar] [CrossRef]