Parallel Strategies for Solving Large Unit Commitment Problems in the California ISO Planning Model

Abstract

We present our study of solving large unit commitment problems in the California ISO planning model. The model calculates hourly day-ahead unit commitments, and all instances need to be solved close to optimality within an hour. It takes CPLEX, the current state-of-the-art solver, up to 5 and 10 hours to solve the deterministic instances and the 5-scenario stochastic instances, respectively. The 20-scenario instances are practically unsolvable as no feasible solutions are found after 24hours.We consider improving solution times through distributed-memory parallelization. Prior techniques such as distributed branch-and-bound perform poorly for our problems. We propose coordinated concurrent search to solve the deterministic instances on a cluster. For stochastic instances, we propose parallelization strategy that combines scenario-based decomposition and asynchronous solves guided by intermediate results from progressive hedging. Our decomposition creates linear sub problems instead of quadratic ones that are oftentimes intractable. On a cluster of 16 IBM Power7 machines, our parallel implementation achieves on average 12.7 and 22 times speedup for the deterministic instances and the5-scenario stochastic instances, respectively. All problems are solved within an hour to near optimality including the previously unsolvable 20-scenario stochastic instances.