On the complexity of the Unit Commitment Problem

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.