TY - GEN
T1 - Parallel Strategies for Solving Large Unit Commitment Problems in the California ISO Planning Model
AU - Cong, Guojing
AU - Meyers, Carol
AU - Rajan, Deepak
AU - Parriani, Tiziano
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/7/17
Y1 - 2015/7/17
N2 - 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.
AB - 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.
KW - Power generation planning
KW - integer linear programming
KW - optimization methods
KW - parallel algorithms
UR - http://www.scopus.com/inward/record.url?scp=84971406138&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2015.49
DO - 10.1109/IPDPS.2015.49
M3 - Conference contribution
AN - SCOPUS:84971406138
T3 - Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015
SP - 710
EP - 719
BT - Proceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium, IPDPS 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 29th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015
Y2 - 25 May 2015 through 29 May 2015
ER -