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.

17 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↗
NASA NTRS1986

On orbital allotments for geostationary satellites

The following satellite synthesis problem is addressed: communication satellites are to be allotted positions on the geostationary arc so that interference does not exceed a given acceptable level by enforcing conservative pairwise satellite separation. A desired location is specified for each satellite, and the objective is to minimize the sum of the deviations between the satellites' prescribed and desired locations. Two mixed integer programming models for the satellite synthesis problem are presented. Four solution strategies, branch-and-bound, Benders' decomposition, linear programming with restricted basis entry, and a switching heuristic, are used to find solutions to example synthesis problems. Computational results indicate the switching algorithm yields solutions of good quality in reasonable execution times when compared to the other solution methods. It is demonstrated that the switching algorithm can be applied to synthesis problems with the objective of minimizing the largest deviation between a prescribed location and the corresponding desired location. Furthermore, it is shown that the switching heuristic can use no conservative, location-dependent satellite separations in order to satisfy interference criteria.

Gonsalvez, David J. A.↗
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↗
NASA NTRS1981

Establishment of terrestrial reference frames by new observational techniques

It is anticipated that terrestrial reference systems for geodynamics studies which include adopted plate motion models will be introduced for the analysis of both LAGEOS satellite and very long baseline interferometry ranging data. One of the possible approaches involves adjustment of ground station coordinates in conjunction with solutions for Universal Time 1 (UT1) and polar motions as functions of time. Another method uses principal value decomposition to reduce the number of degrees of freedom being solved for by three. In a third alternative, the values of UT1 and polar motion derived from the available data by means of the initial set of coordinates are kept fixed, and an appropriate block of data is reanalyzed using the previously determined values of UT1 and polar motion so that a new set of station coordinates can be derived.

Bender, P. L.↗
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↗
NASA NTRS2004

Increasing the Thermal Stability of Aluminum Titanate for Solid Oxide Fuel Cell Anodes

Solid-oxide fuel cells (SOFCs) show great potential as a power source for future space exploration missions. Because SOFCs operate at temperatures significantly higher than other types of fuel cells, they can reach overall efficiencies of up to 60% and are able to utilize fossil fuels. The SOFC team at GRC is leading NASA's effort to develop a solid oxide fuel cell with a power density high enough to be used for aeronautics and space applications, which is approximately ten times higher than ground transport targets. layers must be able to operate as a single unit at temperatures upwards of 900'C for at least 40,000 hours with less than ten percent degradation. One key challenge to meeting this goal arises from the thermal expansion mismatch between different layers. The amount a material expands upon heating is expressed by its coefficient of thermal expansion (CTE). If the CTEs of adjacent layers are substantially different, thermal stresses will arise during the cell's fabrication and operation. These stresses, accompanied by thermal cycling, can fracture and destroy the cell. While this is not an issue at the electrolyte-cathode interface, it is a major concern at the electrolyte-anode interface, especially in high power anode-supported systems. electrolyte are nearly identical. Conventionally, this has been accomplished by varying the composition of the anode to match the CTE of the yittria-stabilized zirconia (YSZ) electrolyte (approx.10.8x10(exp -6/degC). A Ni/YSZ composite is typically used as a base material for the anode due to its excellent electrochemical properties, but its CTE is about 13.4x10(exp -6/degC). One potential way to lower the CTE of this anode is to add a small percentage of polycrystalline Al2TiO5, with a CTE of 0.68x10(exp -6/degC, to the Ni/YSZ base. However, Al2TiO5 is thermally unstable and loses its effectiveness as it decomposes to Al2O3 and TiO2 between 750 C and 1280 C. be used as additives to increase the thermal stability of Al2TiO5 in SOFC operating conditions without adversely affecting the electrochemical properties of the SOFC anode. Three candidate materials were chosen through an extensive literature review: MgO, Fe2O3, and ZrTiO4. Although all three have been shown to prevent Al2TiO5 decomposition under various conditions, their effectiveness in the temperature range and atmosphere of the SOFC has not yet been evaluated. Several batches of Al2TiO5 with varying amounts of additives were prepared, exposed to reducing and oxidizing atmospheres at elevated temperatures, and the resulting decomposition of Al2TiO5 was measured. The most promising additives were further evaluated with the goal of ultimately preparing low CTE anodes that are chemically compatible to current systems. Adding minor constituents to stabilize Al2TiO5 could ultimately preserve its low CTE for the life of the fuel cell and improve the cell's long-term performance without a drop in anode conductivity. Further, these low CTE filler additions could allow the use of new sulfur tolerant anode materials, improving the viability of SOFCs for future aeronautics and space applications. Every SOFC consists of a cathode and an anode separated by an electrolyte, These three One way to avoid this problem is to design the cell such that the CTEs of the anode and The objective of this summer research project was to evaluate several materials that could

Bender, Jeffrey B.↗
NASA NTRS1994

A simple suboptimal least-squares algorithm for attitude determination with multiple sensors

Three-axis attitude determination is equivalent to finding a coordinate transformation matrix which transforms a set of reference vectors fixed in inertial space to a set of measurement vectors fixed in the spacecraft. The attitude determination problem can be expressed as a constrained optimization problem. The constraint is that a coordinate transformation matrix must be proper, real, and orthogonal. A transformation matrix can be thought of as optimal in the least-squares sense if it maps the measurement vectors to the reference vectors with minimal 2-norm errors and meets the above constraint. This constrained optimization problem is known as Wahba's problem. Several algorithms which solve Wahba's problem exactly have been developed and used. These algorithms, while steadily improving, are all rather complicated. Furthermore, they involve such numerically unstable or sensitive operations as matrix determinant, matrix adjoint, and Newton-Raphson iterations. This paper describes an algorithm which minimizes Wahba's loss function, but without the constraint. When the constraint is ignored, the problem can be solved by a straightforward, numerically stable least-squares algorithm such as QR decomposition. Even though the algorithm does not explicitly take the constraint into account, it still yields a nearly orthogonal matrix for most practical cases; orthogonality only becomes corrupted when the sensor measurements are very noisy, on the same order of magnitude as the attitude rotations. The algorithm can be simplified if the attitude rotations are small enough so that the approximation sin(theta) approximately equals theta holds. We then compare the computational requirements for several well-known algorithms. For the general large-angle case, the QR least-squares algorithm is competitive with all other know algorithms and faster than most. If attitude rotations are small, the least-squares algorithm can be modified to run faster, and this modified algorithm is faster than all but a similarly specialized version of the QUEST algorithm. We also introduce a novel measurement averaging technique which reduces the n-measurement case to the two measurement case for our particular application, a star tracker and earth sensor mounted on an earth-pointed geosynchronous communications satellite. Using this technique, many n-measurement problems reduce to less than or equal to 3 measurements; this reduces the amount of required calculation without significant degradation in accuracy. Finally, we present the results of some tests which compare the least-squares algorithm with the QUEST and FOAM algorithms in the two-measurement case. For our example case, all three algorithms performed with similar accuracy.

Brozenec, Thomas F.↗