|
|
一种求解机组组合问题的分支定界方法
|
Abstract:
文章提出一种求解机组组合问题的分支定界方法。利用热率和透视割平面将机组组合模型做近似线性化处理，将混合整数二次规划转化为混合整数线性规划进行求解。为提高分支定界的计算效率，进行上层变量固定并优先搜索机组启停状态最接近0.5的节点。数值结果表明，此法与直接求解混合整数二次规划的发电费用相当，但计算时间占优，适合求解大规模机组组合问题。
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.
| [1] | Padhy, N.P. (2004) Unit Commitment—A Bibliographical Survey. IEEE Transactions on Power Systems, 19, 1196-1205. https://doi.org/10.1109/tpwrs.2003.821611 |
| [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. https://doi.org/10.1007/s00500-019-04445-x |
| [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. https://doi.org/10.1109/tpwrs.2020.2986710 |
| [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. https://doi.org/10.1109/tpwrs.2005.860922 |
| [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. https://doi.org/10.1016/j.egyr.2024.02.004 |
| [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. https://doi.org/10.1016/j.asoc.2024.111845 |
| [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. https://doi.org/10.1109/tpas.1983.317714 |
| [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. https://doi.org/10.1109/tpwrs.2003.811000 |
| [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. https://doi.org/10.1016/j.ijepes.2014.11.025 |
| [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. https://doi.org/10.1109/tpwrs.2023.3287199 |
| [12] | Ongsakul, W. and Petcharaks, N. (2004) Unit Commitment by Enhanced Adaptive Lagrangian Relaxation. IEEE Transactions on Power Systems, 19, 620-628. https://doi.org/10.1109/tpwrs.2003.820707 |
| [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. https://doi.org/10.1007/bf00934810 |
| [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. https://doi.org/10.1109/tpwrs.2013.2253136 |
| [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. https://doi.org/10.1016/j.ijepes.2018.12.043 |
| [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. https://doi.org/10.1109/tpwrs.2008.2004744 |
| [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. https://doi.org/10.1287/ijoc.2019.0944 |
| [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. https://doi.org/10.1109/tpwrs.2006.876672 |
| [21] | Land, A.H. and Doig, A.G. (1960) An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28, 497-520. https://doi.org/10.2307/1910129 |
| [22] | Atamtürk, A. and Savelsbergh, M.W.P. (2005) Integer-Programming Software Systems. Annals of Operations Research, 140, 67-124. https://doi.org/10.1007/s10479-005-3968-2 |
| [23] | Nannicini, G. and Belotti, P. (2011) Rounding-based Heuristics for Nonconvex MINLPs. Mathematical Programming Computation, 4, 1-31. https://doi.org/10.1007/s12532-011-0032-x |
| [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. https://doi.org/10.1109/tpas.1978.354719 |
