Decomposition Methods for Power Grid Optimization

Deepak Rajan (15-ERD-041)

 

Project Description

Electricity production modeling and simulation tools are used extensively by utilities, independent system operators, state utility commissions, and oversight agencies to support major policy and acquisition decisions for the nation's electric grid. Tools currently used by industry were generally designed to model hierarchical, centrally controlled systems with a few large-scale power plants. These tools have not kept pace with the changes in the electric grid such as active consumer participation in markets, small-scale grid storage, and intermittent renewable generation. We plan to develop algorithms tailored for high-performance computing platforms that can solve large-scale optimization problems arising from design and operation of the electric power grid. The current industry practice is to solve highly aggregated models of large parts of the grid comprising many utilities, or independently solve higher-resolution models of individual utilities or components of the system (e.g., transmission and distribution). Neither of these approaches provides a comprehensive basis for making grid investment and operating decisions. We plan to collaborate with industry and universities to demonstrate the solution of relevant large-scale production simulation models using mathematical decomposition methods (solutions of problems and design of algorithms in which the basic idea is to decompose the problem into sub-problems) in conjunction with high-performance computing.

We anticipate that better solutions to problems relevant to production of electrical energy could reduce the approximately $300 billion annual U.S. grid operating costs and lead to better planning and investment decisions for replacement of approximately $800 billion in aging grid infrastructure. More importantly, better coordination among energy utilities could improve reliability and flexibility to assimilate intermittent renewable generators. We expect to work with energy-community collaborators to incorporate new algorithms into commercial software that would exploit multiple-core computational systems to solve problems at hundredfold larger scales or to solve existing problems a hundredfold times faster. We intend to (1) acquire industry models of the power grid; (2) develop spatial and temporal decomposition methods to solve large-scale deterministic optimization problems in continuous variables; (3) introduce binary variables to represent electrical transmission switching and unit on-and-off states, and modify optimization algorithms accordingly; and (4) introduce scenarios to represent uncertainty and develop scenario-based decomposition algorithms.

Mission Relevance

The increased complexity of the power grid from additional intermittent renewable generators and customer participation through demand-and-response programs drives the need for next-generation optimization and control algorithms with orders-of-magnitude enhancements in capabilities. Our research into this capability aligns with the Laboratory's strategic focus area in energy and climate security, as well as the core competency in high-performance computing, simulation, and data science.

FY16 Accomplishments and Results

In FY16 we (1) coupled the high-resolution models from Energy Exemplar Corp., located in northern California, with weather models developed at LLNL to create a model that is 25-times larger than what was previously available by increasing the time and uncertainty resolution; (2) created grid models greater than a hundredfold larger by increasing spatial resolution; (3) developed new decomposition-based algorithms to solve discrete stochastic problems (see figure); (4) developed parallel implementations of our algorithms to leverage high-performance computing architectures; and (4) released a proof-of-concept code PIPS-SBB (Parallel Interior Point Solvers–Simple Branch and Bound) to solve discrete stochastic problems.
Realistic optimization models of the electrical grid must incorporate uncertainty arising from unpredictable renewable sources of electricity because of weather. we solve these so-called stochastic models using decomposition schemes that leverage both data parallelism and task parallelism. each step in the decomposition scheme (represented by a circle in the diagram) corresponds to solving an optimization problem with specific model structure. the structure allows us to exploit data parallelism by distribut
Realistic optimization models of the electrical grid must incorporate uncertainty arising from unpredictable renewable sources of electricity because of weather. We solve these so-called stochastic models using decomposition schemes that leverage both data parallelism and task parallelism. Each step in the decomposition scheme (represented by a circle in the diagram) corresponds to solving an optimization problem with specific model structure. The structure allows us to exploit data parallelism by distributing it across many processors (represented by the computer chips in the diagram). We can also solve many (but not all) steps in the decomposition scheme simultaneously and independently (represented by computer chips for all active steps shown as red circles), exploiting task parallelism.

Publications and Presentations

  • Munguia, L., Oxberry, and G. Rajan, D., "PIPS-SBB: A parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs." Proc. 2016 International Parallel and Distributed Processing Symp. (IPDPS) Workshops. IEEE Computer Society Conference Publishing Service, New York, NY (2016). LLNL-JRNL-678917.
  • Oxberry, G. M., et al., Updates to PIPS-SBB: Distributed-memory structure-aware presolve and cut generation. XIV Intl. Conf. Stochastic Programming, Rio de Janeiro, June 25–July 1, 2016. LLNL-PRES-697105.
  • Oxberry, G. M., et al., Updates to PIPS-SBB: A parallel distributed memory stochastic MIP solver. INFORMS Annual Mtg. 2015, Philadelphia, PA, Nov. 1–4, 2015. LLNL-PRES-678569.
  • Rajan, D., et al., Applying a new scenario decomposition algorithm to solve stochastic unit commitment problems. IEEE Power and Energy Systems General Mtg., Boston, MA, July 17–21, 2016. LLNL-PRES-697122.
  • Rajan, D., et al., PIPS-SBB: A parallel distributed memory solver for stochastic mixed-integer optimization. SIAM Conf. Parallel Processing for Scientific Computing, Paris, France, Apr. 12–15, 2016. LLNL-PRES-688097.
  • Rajan, D. Stochastic integer programming: Parallel distributed-memory algorithms. IMA Research Collaboration Workshop: Optimization and Uncertainty Quantification in Energy and Industrial Applications, Minneapolis, MN, Feb. 22–24. LLNL-PRES-683481.
  • Ryan, K., D. Rajan, and S. Ahmed, "Scenario decomposition for 0-1 stochastic programs: Improvements and asynchronous implementation." Proc. 2016 International Parallel and Distributed Processing Symposium (IPDPS) Workshops. IEEE Computer Society Conference Publishing Service, New York, NY (2016). LLNL-JRNL-678424.
  • Ryan, K., et al., 0-1 stochastic programs: Scenario decomposition and scenario bunching. INFORMS Ann. Mtg., Nashville, TN, Nov. 13–16, 2016. LLNL-PRES-678919.
  • Ryan, K., et al., “Optimization driven scenario bunching. INFORMS J. Comp. (2016). LLNL-JRNL-681105.