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

  • S.C. Fang
  • Ruotian Gao
  • Wenxun Xing
  • Cheng Lu
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Scheduling Tags , , , , Short URL: https://optimization-online.org/?p=16083

    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