Optimization Online


On the complexity of the Unit Commitment Problem

Pascale Bendotti (pascale.bendotti***at***edf.fr)
Pierre Fouilhoux (pierre.fouilhoux***at***lip6.fr)
CÚcile Rottner (cecile.rottner***at***edf.fr)

Abstract: This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods.A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for T=1. The UCP is proved to be strongly NP-hard.When either a unitary cost or amount of power is considered, the UCP is polynomial for T=1 and NP-hard for arbitrary $T$. When the constraints are restricted to minimum up and down times, the UCP is shown to be polynomial for a fixed n. The pricing subproblem commonly used in a UCP decomposition scheme is also shown to be strongly NP-hard for a subset of units.

Keywords: Unit Commitment Problem; Complexity; Subproblem of decomposition scheme

Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences

Citation: Sorbonne UniversitÚs, UniversitÚ Pierre et Marie Curie, LIP6 CNRS UMR 7606, 4 Place Jussieu, 75005 Paris; EDF R&D, 7 Boulevard Gaspard Monge, 91120 Palaiseau, France. May, 2017.

Download: [PDF]

Entry Submitted: 05/19/2017
Entry Accepted: 06/06/2017
Entry Last Modified: 10/30/2017

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