Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Benders decomposition”

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.

13 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Benders Decomposition Using Graph Modeling and Multi-Parametric Programming

Benders decomposition is a widely used method for solving large and structured optimization problems, but its performance is affected by the repeated solution of subproblems. We propose a flexible and modular algorithmic framework for accelerating Benders decomposition. Specifically, we express the problem structure by using a graph-theoretic modeling abstraction in which nodes represent optimization subproblems and edges represent connectivity between subproblems. A key innovation of our approach is that we embed multiparametric programming (mp) surrogates for node subproblems, which maps the exact analytical map of the subproblem solution space. The use of mp surrogates allows us to replace subproblem solves with fast look-ups and function evaluations for primal and dual variables during the iterative Benders process. We formally show the equivalence between classical Benders cuts and those derived from the mp solution. We implement our framework in the open-source PlasmoBenders.jl software package. To demonstrate the capabilities of the proposed framework, we apply it to a two-stage stochastic programming problem, which aims to make optimal capacity expansion decisions under market uncertainty. We evaluate both single-cut and multicut variants of Benders decomposition and show that the use of mp surrogates achieves substantial speedups in subproblem solve time, while preserving the convergence guarantees of Benders decomposition. We highlight advantages in solution analysis and interpretability that is enabled by mp critical region tracking; specifically, we show that these reveal how decisions evolve geometrically across the Benders search. Our results aim to demonstrate that combining surrogate modeling with graph modeling offers a promising and extensible foundation for structure-exploiting decomposition. In addition, by decomposing the problem into more tractable subproblems, the proposed approach also aims to overcome scalability issues of mp. Finally, the use of mp surrogates provides a unifying and modular optimization framework that enables the representation of heterogeneous node subproblems as modeling objects with a homogeneous structure.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Stochastic scheduling of generating units with weekly energy storage: A hybrid decomposition approach

We propose a solution method for the large-scale stochastic unit commitment (SUC) problem with weekly-dispatched energy storage and significant weather-dependent stochastic generating capacity. Weekly storage facilities that mostly charge during weekends and discharge during weekdays require a weekly scheduling of generating units, which result in a large-scale optimization problem. This SUC problem is formulated as a two-stage stochastic model and we use the conditional value-at-risk as a risk measure. Using a Benders framework, the proposed solution method decomposes the problem into a mixed-integer linear master problem and linear and continuous subproblems. The master problem corresponds to the first-stage decisions throughout the week and includes all the commitment (binary) variables and their corresponding constraints. The subproblems correspond to the actual dispatch of the generating units on a weekly basis. Based on the success of column-and-constraint generation algorithms to solve robust optimization problems, we improve the low communication between the master problem and the subproblems in the standard Benders decomposition by adding primal variables and constraints from the subproblems to the master problem, which provides a better approximation of the recourse function. Furthermore, our computational experiments demonstrate the effectiveness of the proposed decomposition method using an instance of the South Carolina synthetic system with 90 generating units under 40 scenarios.

25 ENERGY STORAGE↗
DOE OSTI2022

A computationally efficient algorithm for computing convex hull prices

Electricity markets worldwide allow participants to bid non-convex production offers. While non-convex offers can more accurately reflect a resource's capabilities, they create challenges for market clearing processes. For example, system operators may be required to execute side payments to participants whose costs are not covered through energy sales as determined via traditional locational marginal pricing schemes. Convex hull pricing minimizes this and other types of side payments while providing uniform (i.e., locationally and temporally consistent) prices. Computing convex hull prices involves solving either a large-scale linear program or the Lagrangian dual of the corresponding non-convex scheduling problem. Further, the former approach requires explicit descriptions of market participants' convex hulls. While linear programs for computing convex hull prices are large, their structure is naturally decomposable by generators. Here, in this work, we propose and empirically analyze a Benders decomposition approach to computing convex hull prices that leverages recent advances in convex hull formulations for thermal generating units. We demonstrate across a large set of test instances that our decomposition approach only requires modest computational effort, obtaining solutions at least an order of magnitude faster than the equivalent large-scale linear programming approach. Overall, we provide a computationally feasible method for computing convex hull prices for industrial scale market clearing problems, enabling the possibility of practical adoption of this advanced pricing mechanism.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2022

Hierarchical Distributed Optimal Power Flow of HV and MV Distribution Networks With Continuous and Discrete Devices

With large-scale distributed photovoltaics (PVs) being integrated into distribution networks (DNs), coordinated optimal power flow (OPF) of high voltage (HV) and medium voltage (MV) DNs should be investigated to optimally dispatch the distributed PVs and other network devices. Here, this paper presents a hierarchical distributed OPF method for HV and MV DNs with on-load tap changers, reactive power compensators, feeder switches and distributed PVs. A hierarchical master-slave control architecture is applied to implement coordinated OPF of two-layer DNs. The HV master problem and MV subproblems are transformed into mixed-integer convex problems respectively with second order cone programming and LinDistFlow approximation. Since there is no efficient distributed algorithm to solve such OPF models with integer subproblems, a novel distributed algorithm is proposed in this paper to efficiently solve the hierarchical coordinated OPF model with integer subproblems in a distributed manner. In the proposed algorithm, the coordinated OPF model is solved in a branch-and-bound framework, where in each branch node generalized Benders decomposition (GBD) algorithm is applied to decompose the coordinated OPF model into a master problem and relaxed subproblems and solves them iteratively to get optimal solution. The GBD optimal and feasible cutting planes generated in a branch node are proved to be valid for its descendants. Moreover, three acceleration techniques are introduced into the proposed algorithm to improve computational efficiency. Finally, the effectiveness and accuracy of the proposed method are verified via simulation tests in Jinzhai DNs of China.

42 ENGINEERING↗
DOE OSTI2026

Graph-Based Modeling and Decomposition of Hierarchical Optimization Problems

We present a graph-theoretic modeling approach for hierarchical optimization that leverages the OptiGraph abstraction implemented in the Julia package Plasmo.jl. We show that the abstraction is flexible and can effectively capture complex hierarchical connectivity that arises from decision-making over multiple spatial and temporal scales (e.g., integration of planning, scheduling, and operations in manufacturing and infrastructures). We also show that the graph abstraction facilitates the conceptualization and implementation of decomposition and approximation schemes. Specifically, we propose a graph-based Benders decomposition (gBD) framework that enables the exploitation of hierarchical (nested) structures and that uses graph aggregation/partitioning procedures to discover such structures. In addition, we provide a Julia implementation of gBD, which we call PlasmoBenders.jl. We illustrate the capabilities using examples arising in the context of energy and power systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Optimization under uncertainty of a hybrid waste tire and natural gas feedstock flexible polygeneration system using a decomposition algorithm

Market uncertainties motivate the development of flexible polygeneration systems that are able to adjust operating conditions to favor production of the most profitable product portfolio. However, this operational flexibility comes at the cost of higher capital expenditure. A scenario-based two-stage stochastic nonconvex Mixed-Integer Nonlinear Programming (MINLP) approach lends itself naturally to optimizing these trade-offs. This work studies the optimal design and operation under uncertainty of a hybrid feedstock flexible polygeneration system producing electricity, methanol, dimethyl ether, olefins or liquefied (synthetic) natural gas. A recently developed C++ based software framework (named GOSSIP) is used for modeling the optimization problem as well as its efficient solution using the Nonconvex Generalized Benders Decomposition (NGBD) algorithm. Two different cases are studied: The first uses estimates of the means and variances of the uncertain parameters from historical data, whereas the second assesses the impact of increased uncertain parameter volatility. The value of implementing flexible designs characterized by the value of the stochastic solution (VSS) is in the range of 260–405 M$ for a scale of approximately 893 MW of thermal input. Increased price volatility around the same mean results in higher expected net present value and VSS as operational flexibility allows for asymmetric exploitation of price peaks.

42 ENGINEERING↗
DOE OSTI2024

Multistage Stochastic optimization for mid-term integrated generation and maintenance scheduling of cascaded hydroelectric system with renewable energy uncertainty

The uncertainties resulting from the escalating penetration of renewable energy resources pose severe challenges to the efficient operation of modern power systems. Hydroelectricity is characterized by its flexibility, controllability, and reliability, and thus becomes one of the most ideal energy resources to hedge against such uncertainties. This paper studies the mid-term integrated generation and maintenance scheduling of a cascaded hydroelectric system (CHS) consisting of multiple cascaded reservoirs and hydroelectric units. To precisely describe the mid-term water regulation policies, the hydraulic coupling relationship and water-energy nexus of CHS are incorporated into the proposed optimization model. The uncertainties of natural water inflow and the power outputs of wind/solar energy generation are taken into consideration and captured via a stochastic process modeled by a scenario tree. A multistage stochastic optimization (MSO) approach is developed to coordinate the complementary operations of multiple energy resources, by optimizing the mid-term water resource management, generation scheduling, and maintenance scheduling of CHS. The proposed MSO model is formulated as a large-scale mixed-integer linear program that presents significant computational intractability. To address this issue, a tailored Benders decomposition algorithm is developed. Two real-world case studies are conducted to demonstrate the capability and characteristics of the proposed model and algorithm. The computational results show that the proposed MSO model can exploit the flexibility of hydroelectricity to efficiently respond to variable wind and solar power, and reserve water resources for the generation in peak months to reduce the consumption of fossil fuel. Furthermore, the proposed solution approach also exhibits promising computational efficiency when handling large-scale models.

13 HYDRO ENERGY↗
DOE OSTI2026

SPAROW: Stochastic Programming and Related Optimization Workflows

SAND2026-16703O SPAROW: Stochastic Programming and Related Optimization Workflows is a Python library tool that facilitates the development and solution of stochastic programming problems. It provides a user-friendly class structure for defining stochastic programs through scenario-based representations of uncertainties. SPAROW incorporates multiple optimization strategies, including integer programming with all scenarios, progressive hedging, Benders decomposition, and Snoglode, a novel technique developed by Carnegie Mellon University. It also features interfaces to external solvers and functions that are commonly used in analysis workflows, making it applicable to a wide range of scientific and engineering design challenges, particularly in power grid planning. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Hart, William [Sandia National Lab. (SNL-NM), Albu↗
DOE OSTI2022

A multistage distributionally robust optimization approach to water allocation under climate uncertainty

This paper investigates a Multistage Distributionally Robust Optimization (MDRO) approach to water allocation under climate uncertainty. The MDRO is formed by creating sets of conditional distributions (called conditional ambiguity sets) on a finite scenario tree. The distributions in the conditional ambiguity sets remain close to a nominal conditional distribution according a ø-divergence (e.g., Kullback-Leibler divergence, Hellinger distance, Burg entropy, etc.). Here, the paper discusses a decomposition algorithm to solve the resulting MDRO with ø-divergences, which uses the dual formulation and solves only linear subproblems instead of convex ones. Some properties of the algorithm such as generating feasible policies and valid upper/lower bounds are established. The paper then applies the modeling and solution techniques to allocate water in a rapidly-developing area of Tucson, Arizona. Tucson, like many arid and semi-arid regions around the world, faces considerable uncertainty in its ability to provide water for its citizens in the future. The primary sources of uncertainty in the Tucson region include (1) unpredictable population growth, (2) the availability of water from the Colorado River, and (3) the effects of climate variability on water consumption. This paper integrates forecasts for all these sources of uncertainty into a single optimization model for robust and sustainable water allocation. Then, it uses this model to analyze the value of constructing additional treatment facilities to reduce future water shortages. The results indicate that the MDRO approach can be very valuable for water managers by providing insights to minimize their risks and help them plan for the future.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2023

Small-Signal Angle Stability-Oriented False Data Injection Cyber-Attacks on Power Systems

The small-signal angle stability (SSAS) of a power system is determined by the property of operation points. The widely applied false data injection (FDI) cyber-attack, however, is able to stealthily mislead the optimal power flow (OPF) and thus compromise operation points, leading to damages to the SSAS margin. Here, to provide insights for cyber defenders, this paper proposes and investigates a stealthy SSAS-oriented FDI cyber-attack focusing on two attacking purposes, i.e., the SSAS margin and operation cost, with higher priority on the former one. First, this paper establishes a novel bi-level model with an implicit SSAS constraint based on a structure preserving model to compromise operation points. Then, for the SSAS interarea mode in a typical two-area system, this paper formulates closed-form expressions of how the SSAS margin and operation cost behave with respect to stealthy injections. By comparison, for the SSAS local mode in general power systems, this paper proposes a moving target cyber-attack-based hierarchical solution algorithm. Simulation results on a two-area system, a Kundur 11 bus system, and a modified IEEE 14 bus system demonstrate the significant damaging effects of the proposed SSAS-oriented FDI cyber-attack and the conflict between the two attacking purposes.

Benders decomposition↗
DOE OSTI2023

Capturing Travel Mode Adoption in Designing On-Demand Multimodal Transit Systems

This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154].

Operations Research & Management Science↗
DOE OSTI2025

γIn-beam angular distribution and linear polarization measurements with GRETINA using a simple energy-ordering approach

Angular distribution and linear polarization measurements are powerful tools for inferring the spins and parities of nuclear levels. In this work, the performance of the Gamma-Ray Energy Tracking In-beam Nuclear Array (GRETINA) as a Compton polarimeter was characterized in a fusion-evaporation reaction experiment using a simple energy-ordering approach for the interaction points assigned in the signal decomposition process. A variety of multipolarities and characters for γ-ray transitions in the reaction products 25 Mg, 25 Na, and 22 Ne, formed from fusion-evaporation of an 18 O beam on a 9 Be target, were examined. The experimental angular distributions and linear polarization asymmetries were consistent with predictions using the theoretical formalism accounting for the Lorentz boost.

Angular distribution↗