  


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 NPhard in the ordinary sense even for T=1. The UCP is proved to be strongly NPhard.When either a unitary cost or amount of power is considered, the UCP is polynomial for T=1 and NPhard 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 NPhard 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. Download: [PDF] Entry Submitted: 05/19/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  