A Polynomial-Time Algorithm with Tight Error Bounds for Single-Period Unit Commitment Problem

doi:10.1007/s40305-021-00376-3

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (1): 1-28.doi: 10.1007/s40305-021-00376-3

A Polynomial-Time Algorithm with Tight Error Bounds for Single-Period Unit Commitment Problem

Ruo-Tian Gao¹, Shu-Cherng Fang², Cheng Lu³, Wen-Xun Xing⁴

1 Big Data Center of State Grid Corporation of China, Beijing 100053, China;
2 Department of Industrial and System Engineering, North Carolina State University, Raleigh 27695-7906, USA;
3 School of Economics and Management, North China Electric Power University, Beijing 102206, China;
4 Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Received:2020-12-19 Revised:2021-10-28 Online:2023-03-30 Published:2023-02-28
Contact: Cheng Lu, Ruo-Tian Gao, Shu-Cherng Fang, Wen-Xun Xing E-mail:lucheng1983@163.com;gaort17@tsinghua.org.cn;fang@ncsu.edu;wxing@mail.tsinghua.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos. 11771243, 12171151, and 11701177) and US Army Research Office (No. W911NF-15-1-0223).

Abstract

Abstract: This paper proposes a Lagrangian dual-based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed-integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational results support the effectiveness and efficiency of the proposed algorithm for solving large-scale problems.

Key words: Nonlinear programming, Lagrangian dual, Unit commitment problem, Mixed-integer quadratic programming, Convex relaxation

CLC Number:

Ruo-Tian Gao, Shu-Cherng Fang, Cheng Lu, Wen-Xun Xing. A Polynomial-Time Algorithm with Tight Error Bounds for Single-Period Unit Commitment Problem[J]. Journal of the Operations Research Society of China, 2023, 11(1): 1-28.

TrendMD

References

[1] Tseng, C.L.:On power system generation unit commitment problems, Ph.D.Dissertation, University of California, Berkeley (1996)
[2] Padhy, N.P.:Unit commitment-A bibliographical survey.IEEE Transactions on Power Systems 19, 1196-1205(2004)
[3] Lu, C., Deng, Z., Fang, S.C., Jin, Q., Xing, W.:Fast computation of global solutions to the singleperiod unit commitment problem.Journal of Combinatorial Optimization (2019).https://doi.org/10.1007/s10878-019-00489-9
[4] Galiana, F.D., Motto, A.L., Bouffard, F.:Reconciling social welfare, agent profits, and consumer payments in electricity pools.IEEE Transactions on Power Systems 18, 452-459(2003)
[5] Padberg, M.W., VanRoy, T.J., Wolsey, L.A.:Valid linear inequalities for fixed charge problems.Operations Research 33, 842-861(1985)
[6] Frangioni, A., Gentile, C., Grande, E., Pacifici, A.:Projected perspective reformulations with applications in design problems.Operations Research 59, 1225-1232(2011)
[7] Motto, A.L., Galiana, F.D.:Unit commitment with dual variable constraints.IEEE Transactions on Power Systems 19, 330-338(2004)
[8] Dang, C., Li, M.:A floating-point genetic algorithm for solving the unit commitment problem.European Journal of Operational Research 181, 1370-1395(2007)
[9] Jiang, R., Zhang, M., Li, G., Guan, Y.:Two-stage network constrained robust unit commitment problem.European Journal of Operational Research 234, 751-762(2014)
[10] Rong, A., Hakonen, H., Lahdelma, R.:A variant of the dynamic programming algorithm for unit commitment of combined heat and power systems.European Journal of Operational Research 190, 741-755(2008)
[11] Dai, H., Zhang, N., Su, W.:A literature review of stochastic programming and unit commitment.Journal of Power and Energy Engineering 3, 206-214(2015)
[12] Wu, L., Shahidehpour, M.:Security-constrained unit commitment with uncertainties.In:Chen, Hong (ed.) Power Grid Operation in a Market Environment:Economic Efficiency and Risk Mitigation.John Wiley & Sons, New Jersey (2016).https://doi.org/10.1002/9781119083016.ch5
[13] Tahanan, M., van Ackooij, W., Frangioni, A., Lacalandra, F.:Large-scale unit commitment under uncertainty:A literature survey.4OR Quarterly Journal of the Belgian 13, 115-171(2015)
[14] Yamin, H.Y.:Review on methods of generation scheduling in electric power systems.Electric Power Systems Research 69, 227-248(2004)
[15] Chen, C.L., Wang, S.C.:Branch-and-bound scheduling for thermal generating units.IEEE Transactions on Energy Conversion 8, 184-189(1993)
[16] Huang, K.Y., Yang, H.T., Huang, C.L.:A new thermal unit commitment approach using constraint logic programming, Proceedings of the 20th International Conference on Power Industry Computer Applications, 176-185(1997)
[17] Frangioni, A., Furini, F., Gentile, C.:Approximated perspective relaxations:A project and lift approach.Computational Optimization and Applications 63, 705-735(2016)
[18] Nieva, R., Inda, A., Frausto, J.:CHT:A digital computer package for solving short term hydro-thermal coordinationandunitcommitmentproblems.IEEETransactionsonPowerSystems 1,168-174(1986)
[19] Lowery, P.G.:Generating unit commitment by dynamic programming.IEEE Transactions on Power Apparatus and Systems PAS-85, 422-426(1966)
[20] Schulze, T., Grothey, A., McKinnon, K.:A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems.European Journal of Operational Research 261, 247-259(2017)
[21] Ma, H., Shahidehpour, S.M.:Transmission-constrained unit commitment based on Benders decomposition.International Journal of Electrical Power and Energy Systems 20, 287-294(1998)
[22] Papavasiliou, A., Oren, S.S.:Multiarea stochastic unit commitment for high wind penetration in a tramsimission constrained network.Operations Research 61, 578-592(2013)
[23] Carøe, C.C., Schultz, R.:A two-stage stochastic program for unit commitment under uncertainty in a hydro-thermal power system.Konrad-Zuse-Zentrum für Informationstechnik (1998).https://edocs.tib.eu/files/e001/247354082.pdf
[24] Nowak, M.P., Römisch, W.:Stochastic Lagrangian relaxation applied to power scheduling in a hydrothermal system under uncertainty.Annals of Operations Research 100, 251-272(2000)
[25] Gröwe-Kuska, N., Römisch, W.:Stochastic unit commitment in hydrothermal power production planning, Application of Stochastic Programming, In:S.W.Wallace and W.T.Ziemba (ed.) MOSSIAM Series on Optimization, Chapter 30, 633-653(2005)
[26] Ghaddar, B., Naoum-Sawaya, J., Kishimoto, A., Taheri, N., Eck, B.:A Lagrangian decomposition approach for the pump scheduling problem in water networks.European Journal of Operational Research 241, 490-501(2015)
[27] Dudek, G.:Adaptive simulated annealing schedule to the unit commitment problem.Electric Power Systems Research 80, 465-472(2010)
[28] Mantawy, A.H., Abdel-Magid, Y.L., Selim, S.Z.:Integrating genetic algorithms, tabu search, and simulated annealing for the unit commitment problem.IEEE Transactions on Power Systems 14, 829-836(1999)
[29] Selvi,V.,Umarani,R.:Comparativeanalysisofantcolonyandparticleswarmoptimizationtechniques.International Journal of Computer Applications 5, 1-6(2010)
[30] Nagaraja, M.S.:Optimum generation scheduling for thermal power plants using artificial neural network.International Journal of Electrical and Computer Engineering 1, 135-139(2011)
[31] Clerc, M., Kennedy, J.:The particle swarm-explosion, stability, and convergence in a multidimensional complex space.IEEE Transactions on Evolutionary Computation 6, 58-73(2002)
[32] Ogbe,E.,Li,X.:Anewcrossdecompositionmethodforstochasticmixed-integerlinearprogramming.European Journal of Operational Research 256, 487-499(2017)
[33] van den Bosch, P.P.J., Honderd, G.:A solution of the unit commitment problem via decomposition and dynamic programming.IEEE Transactions on Power Apparatus and Systems PAS-104, 1684-1690(1985)
[34] Padhy, N.P.:Hybrid Models for Unit Commitment Problems, Ph.D.Dissertation, Anna University, Chennai (1997)
[35] Fang, S.C., Xing, W.:Linear conic optimization.Science Press, Beijing (2013)
[36] Rockafellar,R.T.,Wets,R.J.B.:Variationalanalysis,aseriesofcomprehensivestudiesinmathematics, vol.317.Springer, Berlin (2004)
[37] Bazaraa, M.S., Sherali, H.D., Shetty, C.M.:Nonlinear programming? In:Theory and Algorithms, 3rd edn.John Wiley & Sons, New Jersey (2013)

A Polynomial-Time Algorithm with Tight Error Bounds for Single-Period Unit Commitment Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Sumit Kumar Maiti, Sankar Kumar Roy. Bi-level Programming for Stackelberg Game with Intuitionistic Fuzzy Number: a Ranking Approach [J]. Journal of the Operations Research Society of China, 2021, 9(1): 131-149.
[2]	Yong Xia. A Survey of Hidden Convex Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(1): 1-28.
[3]	Murat Adivar, Shu-Cherng Fang. Convex Analysis and Duality over Discrete Domains [J]. Journal of the Operations Research Society of China, 2018, 6(2): 189-247.
[4]	Mrinal Jana · Geetanjali Panda. Compromising Solution of Geometric Programming Problem with Bounded Parameters [J]. Journal of the Operations Research Society of China, 2017, 5(3): 377-390.
[5]	Zhi-You Wu · Fu-Sheng Bai · Jing Tian. Optimization Methods for Box-Constrained Nonlinear Programming Problems Based on Linear Transformation and Lagrange Interpolating Polynomials [J]. Journal of the Operations Research Society of China, 2017, 5(2): 193-.
[6]	Le Han · Xiao-Lan Liu. Convex Relaxation Algorithm for a Structured Simultaneous Low-Rank and Sparse Recovery Problem [J]. Journal of the Operations Research Society of China, 2015, 3(3): 363-.