A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

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.

Citation

Department of Mathematical Sciences, Tsinghua University, Beijing, China

Article

Download

View A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem