Back to Search
Start Over
On the complexity of the Unit Commitment Problem.
- Source :
-
Annals of Operations Research . Mar2019, Vol. 274 Issue 1/2, p119-130. 12p. - Publication Year :
- 2019
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02545330
- Volume :
- 274
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Annals of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 134673602
- Full Text :
- https://doi.org/10.1007/s10479-018-2827-x