1. Home
  2. Report Archives
  3. FY2015 LDRD Annual Report
  4. Energy and Climate Security
  5. Decomposition Methods for Power Grid Optimization

Decomposition Methods for Power Grid Optimization

Deepak Rajan (15-ERD-041)

Abstract

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 will 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. In addition, 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 acquire industry models of the power grid; develop spatial and temporal decomposition methods to solve large-scale deterministic optimization problems in continuous variables; introduce binary variables to represent electrical transmission switching and unit on-and-off states, and modify optimization algorithms accordingly; and 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.

FY15 Accomplishments and Results

In FY15 we (1) obtained high-resolution models of the electrical grid of the western United States from Energy Exemplar Corp., located in northern California; (2) created a model, coupling the high-resolution models from Energy Exemplar with weather models developed at LLNL, that is 25-times larger (by increasing time and uncertainty resolution) than what was previously available; (3) created grid models greater than a hundredfold larger by increasing spatial resolution; and (4) released a proof-of-concept code to solve discrete stochastic problems.

Realistic optimization models of the electrical grid must incorporate uncertainty arising from unpredictable renewable sources of electricity due to weather. we solve these so-called stochastic models using decomposition schemes that leverage both data and task parallelism. each step in the decomposition scheme (represented by a circle on the left-hand side of the diagram) corresponds to solving an optimization problem with specific block-diagonal model structure (represented by the lettered squares). the b
Realistic optimization models of the electrical grid must incorporate uncertainty arising from unpredictable renewable sources of electricity due to weather. We solve these so-called stochastic models using decomposition schemes that leverage both data and task parallelism. Each step in the decomposition scheme (represented by a circle on the left-hand side of the diagram) corresponds to solving an optimization problem with specific block-diagonal model structure (represented by the lettered squares). The block-diagonal structure allows us to exploit data parallelism by distributing it across many processors (represented by the computer chips on the right). We can also solve some (but not all) of the steps in the decomposition simultaneously and independently, exploiting task parallelism.

Publications and Presentations

  • Cong, G., et al., “Parallel strategies for solving large unit commitment problems in the California ISO planning model.” Parallel and Distributed Processing Symposium (IPDPS), 2015 IEEE Intl., p. 710. IEEE, New York, NY (2015). LLNL-CONF-665779.
  • Oxberry, G. M., et al., Distributed memory branch-and-bound for stochastic MILPs using distributed memory simplex for stochastic LPs. 22nd Intl. Symp. Mathematical Programming, Pittsburgh, PA, July 12–17, 2015. LLNL-PRES-674436.
  • Rajan, D., Stochastic mixed-integer programming formulations and algorithms: Examples from electric power generation. IEEE Signal Processing Society Chapter Mtg., Livermore, CA, Aug. 13, 2015. LLNL-PRES-676180.
  • Rajan, D., et al., Solving discrete optimization problems in the electrical grid: New parallel algorithms. 14th INFORMS Computing Society Conf., Richmond, VA, Jan. 11–13, 2015. LLNL-PRES-665929.
  • Ryan, K., S. Ahmed, and D. Rajan, Scenario decomposition for 0-1 stochastic programs: Asynchronous parallel implementation. 22nd Intl. Symp. Mathematical Programming, Pittsburgh, PA, July 12–17, 2015. LLNL-PRES-674353.
  • Ryan, K., D. Rajan, and S. Ahmed, Accelerating scenario decomposition algorithms. 14th INFORMS Computing Society Conf., Richmond, VA, Jan. 11–13, 2015. LLNL-PRES-666117.