The single-period unit commitment problem arises from electricity markets.An efficient global algorithm not only provides the optimal schedulethat achieves the lowest cost, but also plays an important role for deriving the market-clearingprice. As of today, the problem is mainly solved by using a general-purpose mixed-integer quadraticprogramming solver such as CPLEX or Gurobi. This paper proposes an extremely efficient global optimization algorithmfor solving the problem. We propose a conjugate function based convex relaxation and design a special dual algorithm to compute a tight lower boundof the problem in O(nlogn) complexity. Then, a branch-and-boundalgorithm is designed for finding a global solution to the problem. Computational experimentsshow that the proposed algorithm solves test instances with 500 integer variablesin less than 0.01 seconds, whereas current state-of-the-art solvers fail to solve the sametest instances in one hour. This superior performance of the proposed algorithm clearly indicates its potential in day-ahead and real-time electricity markets.
