Search NASA⌕ Search

SEARCH · Search NASA

Results for “Stochastic programming”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 109 records · Page 6

New bounding and decomposition approaches for MILP investment problems: Multi-area transmission and generation planning under policy constraints

A novel two-phase bounding and decomposition approach to compute optimal and near-optimal solutions to large-scale mixed-integer investment planning problems is proposed and it considers a large number of operating subproblems, each of which is a convex optimization. Our motivating application is the planning of power transmission and generation in which policy constraints are designed to incentivize high amounts of intermittent generation in electric power systems. The bounding phase exploits Jensen’s inequality to define a lower bound, which we extend to stochastic programs that use expected-value constraints to enforce policy objectives. The decomposition phase, in which the bounds are tightened, improves upon the standard Benders’ algorithm by accelerating the convergence of the bounds. The lower bound is tightened by using a Jensen’s inequality-based approach to introduce an auxiliary lower bound into the Benders master problem. Upper bounds for both phases are computed using a sub-sampling approach executed on a parallel computer system. Numerical results show that only the bounding phase is necessary if loose optimality gaps are acceptable. But, the decomposition phase is required to attain optimality gaps. Moreover, use of both phases performs better, in terms of convergence speed, than attempting to solve the problem using just the bounding phase or regular Benders decomposition separately.

97 MATHEMATICS AND COMPUTING↗

Resource distribution under spatiotemporal uncertainty of disease spread: Stochastic versus robust approaches

We consider the problem of optimizing locations of distribution centers (DCs) and plans for distributing resources such as test kits and vaccines, under spatiotemporal uncertainties of disease spread and demand for the resources. We aim to balance the operational cost (including costs of deploying facilities, shipping, and storage) and quality of service (reflected by demand coverage), while ensuring equity and fairness of resource distribution across multiple populations. We compare a sample-based stochastic programming (SP) approach with a distributionally robust optimization (DRO) approach using a moment-based ambiguity set. Numerical studies are conducted on instances of distributing COVID-19 vaccines in the United States and test kits, to compare SP and DRO models with a deterministic formulation using estimated demand and with the current resource distribution plans implemented in the US. We demonstrate the results over distinct phases of the pandemic to estimate the cost and speed of resource distribution depending on scale and coverage, and show the “demand-driven” properties of the SP and DRO solutions. Furthermore, our results further indicate that if the worst-case unmet demand is prioritized, then the DRO approach is preferred despite of its higher overall cost. Nevertheless, the SP approach can provide an intermediate plan under budgetary restrictions without significant compromises in demand coverage.

97 MATHEMATICS AND COMPUTING↗

Modular supply chain optimization considering demand uncertainty to manage risk

Supply chain under demand uncertainty has been a challenging problem due to increased competition and market volatility in modern markets. Flexibility in planning decisions makes modular manufacturing a promising way to address this problem. We report the problem of multiperiod process and supply chain network design is considered under demand uncertainty. A mixed integer two-stage stochastic programming problem is formulated with integer variables indicating the process design and continuous variables to represent the material flow in the supply chain. The problem is solved using a rolling horizon approach. Benders decomposition is used to reduce the computational complexity of the optimization problem. To promote risk-averse decisions, a downside risk measure is incorporated in the model. The results demonstrate the several advantages of modular designs in meeting product demands. A pareto-optimal curve for minimizing the objectives of expected cost and downside risk is obtained.

42 ENGINEERING↗

Optimization under Uncertainty for Water Consumption in a Pulverized Coal Power Plant

Pulverized coal (PC) power plants are widely recognized as major water consumers whose operability has started to be affected by drought conditions across some regions of the country. Water availability will further restrict the retrofitting of existing PC plants with water-expensive carbon capture technologies. Therefore, national efforts to reduce water withdrawal and consumption have been intensified. Water consumption in PC plants is strongly associated to losses from the cooling water cycle, particularly water evaporation from cooling towers. Accurate estimation of these water losses requires realistic cooling tower models, as well as the inclusion of uncertainties arising from atmospheric conditions. In this work, the cooling tower for a supercritical PC power plant was modeled as a humidification operation and used for optimization under uncertainty. Characterization of the uncertainty (air temperature and humidity) was based on available weather data. Process characteristics including boiler conditions, reactant ratios, and pressure ratios in turbines were calculated to obtain the minimum water consumption under the above mentioned uncertainties. In this study, the calculated conditions predicted up to 12% in reduction in the average water consumption for a 548 MW supercritical PC power plant simulated using Aspen Plus. Optimization under uncertainty for these large-scale PC plants cannot be solved with conventional stochastic programming algorithms because of the computational expenses involved. In this work, we discuss the use of a novel better optimization of nonlinear uncertain systems (BONUS) algorithm which dramatically decreases the computational requirements of the stochastic optimization.

01 COAL, LIGNITE, AND PEAT↗

Optimization Under Uncertainty for Water Consumption in a Pulverized Coal Power Plant

Pulverized coal (PC) power plants are widely recognized as major water consumers whose operability has started to be affected by drought conditions across some regions of the country. Water availability will further restrict the retrofitting of existing PC plants with water-expensive carbon capture technologies. Therefore, national efforts to reduce water withdrawal and consumption have been intensified. Water consumption in PC plants is strongly associated to losses from the cooling water cycle, particularly water evaporation from cooling towers. Accurate estimation of these water losses requires realistic cooling tower models, as well as the inclusion of uncertainties arising from atmospheric conditions. In this work, the cooling tower for a supercritical PC power plant was modeled as a humidification operation and used for optimization under uncertainty. Characterization of the uncertainty (air temperature and humidity) was based on available weather data. Process characteristics including boiler conditions, reactant ratios, and pressure ratios in turbines were calculated to obtain the minimum water consumption under the above mentioned uncertainties. In this study, the calculated conditions predicted up to 12% in reduction in the average water consumption for a 548 MW supercritical PC power plant simulated using Aspen Plus. Optimization under uncertainty for these large-scale PC plants cannot be solved with conventional stochastic programming algorithms because of the computational expenses involved. In this work, we discuss the use of a novel better optimization of nonlinear uncertain systems (BONUS) algorithm which dramatically decreases the computational requirements of the stochastic optimization.

01 COAL, LIGNITE, AND PEAT↗

Impacts of floating-point non-associativity on reproducibility for HPC and deep learning applications

Run to run variability in parallel programs caused by floating-point non-associativity has been known to significantly affect reproducibility in iterative algorithms, due to accumulating errors. Non-reproducibility can critically affect the efficiency and effectiveness of correctness testing for stochastic programs. Recently, the sensitivity of deep learning training and inference pipelines to floating-point non-associativity has been found to sometimes be extreme. It can prevent certification for commercial applications, accurate assessment of robustness and sensitivity, and bug detection. New approaches in scientific computing applications have coupled deep learning models with high-performance computing, leading to an aggravation of debugging and testing challenges. Here we perform an investigation of the statistical properties of floating-point non-associativity within modern parallel programming models, and analyze performance and productivity impacts of replacing atomic operations with deterministic alternatives on GPUs. We examine the recently-added deterministic options in PyTorch within the context of GPU deployment for deep learning, uncovering and quantifying the impacts of input parameters triggering run to run variability and reporting on the reliability and completeness of the documentation. Finally, we evaluate the strategy of exploiting automatic determinism that could be provided by deterministic hardware, using the Groq LPUTM accelerator for inference portions of the deep learning pipeline. We demonstrate the benefits that a hardware-based strategy can provide within reproducibility and correctness efforts.

Shanmugavelu, Sanjif↗

A Data-Driven Methodology for Contextual Unit Commitment Using Regression Residuals

Day after day, system operators are faced with the challenge of taking unit commitment (UC) decisions under uncertain net load conditions. The standard operating procedure for taking UC decisions begins by leveraging auxiliary data on covariates (such as the day of the week or latest weather information) to generate a point prediction for net load, which is used in solving a deterministic UC problem. Such an approach, however, is known to deliver a notoriously poor out-of-sample (OOS) performance, as it completely disregards the stochastic nature of net load. While stochastic programming models explicitly represent uncertainty, they mostly do so using a generic set of scenarios that neglect covariate observations, squandering useful auxiliary data that could be harnessed to glean insights into uncertainty. In this article, we discuss a contextual stochastic optimization approach to UC, which effectively exploits covariate observations while explicitly assessing uncertainty so as to boost the OOS performance of UC decisions. The key thrust of our approach is to leverage regression models, along with their empirical residuals, to set up and solve sample average approximation problems. Not only do we prove that our approach satisfies the requisite conditions for asymptotic optimality and consistency laid out in (Kannan et al., 2022), but we also assess its performance on several case studies conducted using real-world data collected in California ISO and New York ISO grids. In conclusion, results show that the proposed approach can significantly improve OOS performance compared to alternative methods proposed in the literature under varying dataset sizes.

Yurdakul, Ogun↗

An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians

In this study, we consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method Lucidi developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure Paquette and Scheinberg into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive algorithm.

97 MATHEMATICS AND COMPUTING↗

Optimizing Power Line Undergrounding Decisions under Varying Wildfire Risk and Weather Scenarios

Abstract—The threat of wildfire ignitions from electric power equipment has led utilities to increasingly turn to preemptive power shutoffs, which, while effective in reducing grid-induced wildfire risk, can cause significant load loss. Undergrounding power lines is an alternative strategy for preventing grid-induced wildfires. However, undergrounding lines is costly, so an efficient undergrounding plan must balance reductions in wildfire risk and load loss with the cost of undergrounding lines. We propose a robust optimization model to identify which power lines to underground to maximize load served while limiting wildfire risk across a range of wildfire risk and weather scenarios. Since solving this problem may be computationally heavy for large power grids and many operating scenarios, we present a delayed constraint generation algorithm to iteratively add scenarios until an optimal solution is found. We evaluate the performance of this framework on the RTS-GMLC with scenarios representing a year of operating conditions and compare it with a stochastic programming formulation. Our results indicate that our undergrounding model is successful in reducing load shed and risk compared to baseline cases in which no mitigation action is taken and only power shutoffs are implemented (no undergrounding). The robust formulation also reduces more load shed than the stochastic formulation in the most extreme scenarios. Index Terms—grid resilience, optimization, transmission systems, underground power lines, wildfire risk.

Taylor, S. [Department of Electrical and Computer ↗

A Sequential Quadratic Programming Algorithm for Nonsmooth Problems with Upper- \({\boldsymbol{\mathcal{C}^2}}\) Objective

An optimization algorithm for nonsmooth nonconvex constrained optimization problems with upper- \({\boldsymbol{\mathcal{C}^2}}\) objective functions is proposed and analyzed. Upper- \({\boldsymbol{\mathcal{C}^2}}\) is a weakly concave property that exists in difference of convex (DC) functions and arises naturally in many applications, particularly certain classes of solutions to parametric optimization problems e.g., recourse of stochastic programming and projection onto closed sets. The algorithm can be viewed as an extension of sequential quadratic programming (SQP) to nonsmooth problems with upper- \({\boldsymbol{\mathcal{C}^2}}\) objectives or a simplified bundle method. It is globally convergent with bounded algorithm parameters that are updated with a trust-region criterion. The algorithm handles general smooth constraints through linearization and uses a line search to ensure progress. The potential inconsistencies from the linearization of the constraints are addressed through a penalty method. In conclusion, the capabilities of the algorithm are demonstrated by solving both simple upper- \({\boldsymbol{\mathcal{C}^2}}\) problems and a real-world optimal power flow problem used in current power grid industry practices.

97 MATHEMATICS AND COMPUTING↗

Next-Generation Optimization under Uncertainty: Structure-Oriented Algorithms

With the advent of the smart grid, renewable technologies, and carbon emission programs, a key concern is the coordination of national infrastructures such as the electricity, natural gas, and water supply network systems. Anticipating and mitigating uncertainty of weather, demands, and contingencies in a more integrated environment is necessary to maximize resource efficiency and prevent cascading failures that can ultimately lead to catastrophic shortages of supplies. This project developed scalable algorithms for stochastic optimization capable of addressing extreme-scale problems (motivated by challenges in the design and operation of national infrastructures). Specifically, the project developed a new family of algorithms to solve continuous stochastic problems to local and global optimality as well as algorithms to solve mixed-integer convex and nonconvex stochastic programs. We developed supporting local and global convergence theory for these algorithms and implemented the algorithms in open-source software packages that can leverage high-performance computing architectures.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Scalable Preconditioning of Block-Structured Linear Algebra Systems using ADMM

In this paper, we study the solution of block-structured linear algebra systems arising in optimization by using iterative solution techniques. These systems are the core computational bottleneck of many problems of interest such as parameter estimation, optimal control, network optimization, and stochastic programming. Our approach uses a Krylov solver (GMRES) that is preconditioned with an alternating method of multipliers (ADMM). We show that this ADMM-GMRES approach overcomes well-known scalability issues of Schur complement decomposition in problems that exhibit a high degree of coupling. The effectiveness of the approach is demonstrated using linear systems that arise in stochastic optimal power flow problems and that contain up to 2 million total variables and 4,000 coupling variables. We find that ADMM-GMRES is nearly an order of magnitude faster than Schur complement decomposition. Moreover, we demonstrate that the approach is robust to the selection of the augmented Lagrangian penalty parameter, which is a key advantage over the direct use of ADMM.

97 MATHEMATICS AND COMPUTING↗

Marine energy supported multi-energy system planning and operation optimization for sustainable coastal community

The growing need for sustainable energy solutions in coastal areas necessitates the development of integrated systems that leverage abundant marine resources. In this study, a standalone Marine Energy Supported Multi-Energy System (MRE-MES) is designed for sustainable coastal community development, utilizing renewable marine resources, including offshore wind, wave, and solar energy, to address the energy needs of electricity, heat, freshwater, and hydrogen. The proposed MRE-MES incorporates a co-optimization model that simultaneously balances capacity planning and operational efficiency to minimize costs and environmental impacts. The system is tested under different renewable energy penetration levels and demand uncertainties, using a two-stage stochastic programming to account for variability in renewable resources and consumption needs. The experimental results indicate that in the optimal system capacity configuration, the percentage of total renewable energy generation is around 80 %, with or without capacity limitation constraints on PV, water tank, and hydrogen storage. Compared to the worst-case scenario in Monte Carlo experiments, two-stage stochastic optimization results in a more robust decision that effectively mitigates the risks posed by future uncertain demand conditions. In conclusion, the findings highlight the viability of marine energy for providing a resilient, comprehensive energy solution to coastal communities.

Capacity planning↗

Quantifiably secure power grid operation, management, and evolution :

This report summarizes findings and results of the Quantifiably Secure Power Grid Operation, Management, and Evolution LDRD. The focus of the LDRD was to develop decisionsupport technologies to enable rational and quantifiable risk management for two key grid operational timescales: scheduling (day-ahead) and planning (month-to-year-ahead). Risk or resiliency metrics are foundational in this effort. The 2003 Northeast Blackout investigative report stressed the criticality of enforceable metrics for system resiliency the grid s ability to satisfy demands subject to perturbation. However, we neither have well-defined risk metrics for addressing the pervasive uncertainties in a renewable energy era, nor decision-support tools for their enforcement, which severely impacts efforts to rationally improve grid security. For day-ahead unit commitment, decision-support tools must account for topological security constraints, loss-of-load (economic) costs, and supply and demand variability especially given high renewables penetration. For long-term planning, transmission and generation expansion must ensure realized demand is satisfied for various projected technological, climate, and growth scenarios. The decision-support tools investigated in this project paid particular attention to tailoriented risk metrics for explicitly addressing high-consequence events. Historically, decisionsupport tools for the grid consider expected cost minimization, largely ignoring risk and instead penalizing loss-of-load through artificial parameters. The technical focus of this work was the development of scalable solvers for enforcing risk metrics. Advanced stochastic programming solvers were developed to address generation and transmission expansion and unit commitment, minimizing cost subject to pre-specified risk thresholds. Particular attention was paid to renewables where security critically depends on production and demand prediction accuracy. To address this concern, powerful filtering techniques for spatio-temporal measurement assimilation were used to develop short-term predictive stochastic models. To achieve uncertaintytolerant solutions, very large numbers of scenarios must be simultaneously considered. One focus of this work was investigating ways of reasonably reducing this number.

Gray, Genetha Anne.↗

A preconditioning technique for Schur complement systems arising in stochastic optimization

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time.

99 GENERAL AND MISCELLANEOUS↗

Scalable Energy System Expansion Under Uncertainty Using Multi-Stage Stochastic Optimization

The intermittent nature of power from renewable energy sources poses new challenges for electrical grids. This is due to the variable and uncertain nature of the power output from these resources. These features of renewable generation are becoming more relevant to energy system planning as grids reach higher penetration levels of renewable energy. In this presentation we present approaches for energy system planning based on scalable computational approaches which enable the explicit consideration of operational uncertainties in the planning process. Using multi-stage stochastic programming and the progressive hedging algorithm, we compute energy system expansion decisions on modified versions of the RTS-GMLC test system augmented with large amounts of renewable generation.

MATHEMATICS AND COMPUTING↗