Deepak Rajan (15-ERD-041)
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.
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 ResultsIn 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.
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.