We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the complexity of the Unit Commitment Problem.
- Authors
Bendotti, Pascale; Fouilhoux, Pierre; Rottner, Cécile
- 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 main result of this article is that the UCP is strongly NP-hard. When the constraints are restricted to minimum up and down times, the UCP is shown to be polynomial for a fixed n. When either a unitary cost or amount of power is considered, the UCP is polynomial for T=1 and strongly NP-hard for arbitrary T. The pricing subproblem commonly used in a UCP decomposition scheme is also shown to be strongly NP-hard for a subset of units.
- Subjects
UNIT commitment problem (Electric power systems); KNAPSACK problems; DYNAMIC programming; DISCRETE time filters; POLYTOPES; GEOMETRIC vertices
- Publication
Annals of Operations Research, 2019, Vol 274, Issue 1/2, p119
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/s10479-018-2827-x