Fast computation of global solutions to the single-period unit commitment problem

Cheng Lu, Zhibin Deng (), Shu-Cherng Fang, Qingwei Jin and Wenxun Xing
Additional contact information
Cheng Lu: North China Electric Power University
Zhibin Deng: Chinese Academy of Sciences
Shu-Cherng Fang: North Carolina State University
Qingwei Jin: Zhejiang University
Wenxun Xing: Tsinghua University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 3, No 6, 1536 pages

Abstract: Abstract The single-period unit commitment problem has significant applications in electricity markets. An efficient global algorithm not only provides the optimal schedule that achieves the lowest cost, but also plays an important role for deriving the market-clearing price. As of today, the problem is mainly solved by using a general-purpose mixed-integer quadratic programming solver such as CPLEX or Gurobi. This paper proposes an extremely efficient global optimization algorithm for solving the problem. We propose a conjugate function based convex relaxation and design a special dual algorithm to compute a tight lower bound of the problem in $${\mathcal {O}}(n\log n)$$ O ( n log n ) complexity. Then, a branch-and-bound algorithm is designed for finding a global solution to the problem. Computational experiments show that the proposed algorithm solves test instances with 500 integer variables in less than 0.01 s, whereas current state-of-the-art solvers fail to solve the same test instances in one hour. This superior performance of the proposed algorithm clearly indicates its potential in day-ahead and real-time electricity markets.

Keywords: Mixed-integer pogramming; Quadratic programming; Branch-and-bound algorithm; 90C11; 90C20; 90C27 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00489-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:3:d:10.1007_s10878-019-00489-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00489-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().