In this talk, I will present an overview of some recent research solving large-scale Unit Commitment problems from the electrical grid, with a focus on parallel algorithms. We consider a planning model that represents the Western Energy Coordinating Council grid, modeled as a mixed-integer linear program (MILP) with hundreds of thousands of variables and constraints for the deterministic version. The stochastic model is a two-stage stochastic optimization extension of the deterministic model.

To solve the deterministic models, we propose a parallelization strategy featuring coordinated concurrent MILP tree search. On a cluster of 16 IBM Power7 machines, our implementation achieves an average 12 times speedup. We are also able to solve all deterministic instances within an hour on a single Power7 machine. To solve the stochastic models, we propose a parallelization strategy based on progressive hedging (PH) that features MILP subproblems and guided MILP solves for finding feasible solutions. On 5-scenario instances, our implementation produces near-optimal solutions with over 20 times speedup; for previously unsolvable 20-scenario stochastic problems, we obtain near-optimal solutions within an hour.  Finally, I will conclude with some work in progress: A new exact scenario decomposition algorithm for solving stochastic unit commitment models.