Polynomial time algorithms and extended formulations for unit commitment problems

Abstract

Recently, increasing penetration of renewable energy generation has created challenges for power system operators to perform efficient power generation daily scheduling, due to the intermittent nature of the renewable generation and discrete decisions of each generation unit. Among all aspects to be considered, a unit commitment polytope is fundamental and embedded in the models at different stages of power system planning and operations. In this article, we focus on deriving polynomial-time algorithms for the unit commitment problems with a general convex cost function and piecewise linear cost function, respectively. We refine an $\mathcal{O}\left(T^3\right)$ time, where T represents the number of time periods, algorithm for the deterministic single-generator unit commitment problem with a general convex cost function and accordingly develop an extended formulation in a higher-dimensional space that can provide an integral solution, in which the physical meanings of the decision variables are described. This means the original problem can be solved as a convex program instead of a mixed-integer convex program. Furthermore, for the case in which the cost function is piecewise linear, by exploring the optimality conditions, we derive more efficient algorithms for both deterministic (i.e., $\mathcal{O}\left(T\right)$ time) and stochastic (i.e., $\mathcal{O}\left(N\right)$ time, where N represents the number of nodes in the stochastic scenario tree) single-generator unit commitment problems. We also develop the corresponding extended formulations for both deterministic and stochastic single-generator unit commitment problems that solve the original mixed-integer linear programs as linear programs. Similarly, physical meanings of the decision variables are explored to show the insights of the new modeling approach.

Keywords:

• Unit commitment
• polynomial-time algorithm
• integral formulation

View correction statement:

Correction

Acknowledgments

The authors thank the editor and the anonymous referees for their sincere suggestions on improving the quality of this article.

Additional information

Funding

The work of K. Pan was partially supported by Hong Kong Polytechnic University under grants 1-ZE73 and G-UABE.

Notes on contributors

Yongpei Guan

Yongpei Guan is a professor and the Director of the Computational and Stochastic Optimization Lab in the Department of Industrial & Systems Engineering at the University of Florida. He received his dual B.S. degrees in mechanical engineering and economic decision science from Shanghai Jiao Tong University in 1998, his M.S. degree in industrial engineering and engineering management from the Hong Kong University of Science and Technology in 2001, and his Ph.D. degree in industrial and systems engineering from the Georgia Institute of Technology in 2005. Presently, his research interests include stochastic and discrete optimization, data-driven stochastic optimization, supply chain management, and renewable energy integration.

Kai Pan

Kai Pan is an Assistant Professor in the Department of Logistics and Maritime Studies at the Hong Kong Polytechnic University. He obtained his B.S. degree in industrial engineering from Zhejiang University in 2010 and his Ph.D. degree from the Department of Industrial & Systems Engineering at the University of Florida in 2016. His research interests include stochastic integer programming and data-driven optimization with applications in power system operations, transportation system scheduling, and supply chain management.

Kezhuo Zhou

Kezhuo Zhou is a Ph.D. student with the Department of Industrial and Systems Engineering at the University of Florida. Before that, he obtained a bachelor's degree from the School of Mathematical Sciences at Fudan University in 2013.