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