Optimization Online


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

Ruotian Gao(gaort17***at***mails.tsinghua.edu.cn)
Shu-Cherng Fang(fang***at***ncsu.edu)
Cheng Lu(lucheng1983***at***163.com)
Wenxun Xing(wxing***at***tsinghua.edu.cn)

Abstract: 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.

Keywords: nonlinear programming, Lagrangian dual, unit commitment problem, mixed integer quadratic programming, convex relaxation

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Applications -- OR and Management Sciences (Scheduling )

Citation: Department of Mathematical Sciences, Tsinghua University, Beijing, China

Download: [PDF]

Entry Submitted: 11/01/2019
Entry Accepted: 11/01/2019
Entry Last Modified: 11/01/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society