Search NASA⌕ Search

Engineering topics

Woodruff, David L.

Publications and source records attributed to Woodruff, David L..

At least 19 records

A parallel hub-and-spoke system for large-scale scenario-based optimization under uncertainty

Practical solution of stochastic programming problems generally requires the use of parallel computing resources. Here, we describe the open source package mpi-sppy, in which efficient and scalable parallelization is a central feature. We report computational experiments that demonstrate the ability to solve very large stochastic programming problems - including mixed-integer variants - in minutes of wall clock time, efficiently leveraging significant parallel computing resources. We report results for the largest publicly available instances of stochastic mixed-integer unit commitment problems, solving to provably tight optimality gaps. In addition, we introduce a novel software architecture that facilitates combinations of methods for accelerating convergence that can be combined in plug-and-play manner. Finally, the mpi-sppy package is written in Python, leverages the widely used Pyomo (http://www.pyomo.org) library for modeling mathematical programs, builds on existing MPI implementations to ensure efficiency and scalability, and is available via http://github.com/Pyomo/mpi-sppy.

97 MATHEMATICS AND COMPUTING↗

Projective Hedging Algorithms for Multistage Stochastic Programming, Supporting Distributed and Asynchronous Implementation

Here we propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those methods. Our derivation assures convergence for convex problems whose feasible set is compact, subject to some standard regularity conditions and a mild “fairness” condition on subproblem selection. The method’s convergence guarantees are deterministic and do not require randomization, in contrast to other proposed asynchronous variations of progressive hedging. Computational experiments described in an online appendix show the method to outperform progressive hedging on large-scale problems in a highly parallel computing environment.

97 MATHEMATICS AND COMPUTING↗

State-of-the-Art Techniques for Large-Scale Stochastic Unit Commitment

Recent advances in deterministic unit commitment, both formulaic and algorithmic, along with modern algorithmic approaches for stochastic programming, have enabled the solution of stochastic unit commitment problems with hundreds of scenarios on large-scale transmission networks. In this presentation, we will give an overview of these methods, including lazy transmission constraint generation, lower-bounding techniques, and heuristics, all of which can be executed in concert with customized decomposition approaches for optimization under uncertainty. We demonstrate the effectiveness of these techniques on the TAMU Texas7K synthetic transmission network, leveraging realistic high-resolution forecasts based on NREL renewable resource availability data. The software leveraged for these demonstrations is available via the open-source software packages EGRET (for electrical grid optimization) and mpi-sppy (for optimization under uncertainty).

27 ARPA - Advanced Research Projects Agency-Energy↗

Assessment of wind power scenario creation methods for stochastic power systems operations

Probabilistic scenarios of renewable energy production, such as wind, have been gaining popularity for use in stochastic variants of power systems operations scheduling problems, allowing for optimal decision-making under uncertainty. The quality of the scenarios has a direct impact on the value of the resulting decisions, but until now, methods for creating scenarios have not been compared under realistic operational conditions. Here, we compare the quality of scenario sets created using three different methods, based on a simulated re-enactment of stochastic day-ahead unit commitment and subsequent dispatch for a realistic test system. We create scenarios using a dataset of forecasted and actual wind power values, scaled to evaluate the effects of increasing wind penetration levels. We show that the choice of scenario set can significantly impact system operating cost, renewable energy use, and the ability of the system to meet demand. This result has implications for the ability of system operators to efficiently integrate renewable production into their day-ahead planning, highlighting the need for the use of performance-based assessments for scenario evaluation.

17 WIND ENERGY↗

Mape Maker: A Scenario Creator

We describe algorithms for creating probabilistic scenarios for the situation when the underlying forecast methodology is modeled as being more (or less) accurate than it has been historically. Such scenarios can be used in studies that extend into the future and may need to consider the possibility that forecast technology will improve. Our approach can also be used to generate alternative realizations of renewable energy production that are consistent with historical forecast accuracy, in effect serving as a method for creating families of realistic alternatives — which are often critical in simulation-based analysis methodologies.

42 ENGINEERING↗

Constructing probabilistic scenarios for wide-area solar power generation

Optimizing thermal generation commitments and dispatch in the presence of high penetrations of renewable resources such as solar energy requires a characterization of their stochastic properties. In this study, we describe novel methods designed to create day-ahead, wide-area probabilistic solar power scenarios based only on historical forecasts and associated observations of solar power production. Each scenario represents a possible trajectory for solar power in next-day operations with an associated probability computed by algorithms that use historical forecast errors. Scenarios are created by segmentation of historic data, fitting non-parametric error distributions using epi-splines, and then computing specific quantiles from these distributions. Additionally, we address the challenge of establishing an upper bound on solar power output. Our specific application driver is for use in stochastic variants of core power systems operations optimization problems, e.g., unit commitment and economic dispatch. These problems require as input a range of possible future realizations of renewables production. However, the utility of such probabilistic scenarios extends to other contexts, e.g., operator and trader situational awareness. Finally, we compare the performance of our approach to a recently proposed method based on quantile regression, and demonstrate that our method performs comparably to this approach in terms of two widely used methods for assessing the quality of probabilistic scenarios: the Energy score and the Variogram score.

14 SOLAR ENERGY↗

Generating short-term probabilistic wind power scenarios via nonparametric forecast error density estimators: Generating short-term probabilistic wind power scenarios via nonparametric forecast error density estimators

Forecasts of available wind power are critical in key electric power systems operations planning problems, including economic dispatch and unit commitment. Such forecasts are necessarily uncertain, limiting the reliability and cost effectiveness of operations planning models based on a single deterministic or “point” forecast. A common approach to address this limitation involves the use of a number of probabilistic scenarios, each specifying a possible trajectory of wind power production, with associated probability. We present and analyze a novel method for generating probabilistic wind power scenarios, leveraging available historical information in the form of forecasted and corresponding observed wind power time series. We estimate non-parametric forecast error densities, specifically using epi-spline basis functions, allowing us to capture the skewed and non-parametric nature of error densities observed in real-world data. We then describe a method to generate probabilistic scenarios from these basis functions that allows users to control for the degree to which extreme errors are captured.We compare the performance of our approach to the current state-of-the-art considering publicly available data associated with the Bonneville Power Administration, analyzing aggregate production of a number of wind farms over a large geographic region. Finally, we discuss the advantages of our approach in the context of specific power systems operations planning problems: stochastic unit commitment and economic dispatch. Here, our methodology is embodied in the joint Sandia – University of California Davis Prescient software package for assessing and analyzing stochastic operations strategies.

17 WIND ENERGY↗

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. Additionally, to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.

97 MATHEMATICS AND COMPUTING↗