On the complexity of the Unit Commitment Problem
Pascale Bendotti (pascale.bendottiedf.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.
Entry Submitted: 05/19/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|