Search NASA⌕ Search

SEARCH · Search NASA

Results for “Heuristic Optimization”

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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
NASA NTRS1991

Intelligent perturbation algorithms for space scheduling optimization

Intelligent perturbation algorithms for space scheduling optimization are presented in the form of the viewgraphs. The following subject areas are covered: optimization of planning, scheduling, and manifesting; searching a discrete configuration space; heuristic algorithms used for optimization; use of heuristic methods on a sample scheduling problem; intelligent perturbation algorithms are iterative refinement techniques; properties of a good iterative search operator; dispatching examples of intelligent perturbation algorithm and perturbation operator attributes; scheduling implementations using intelligent perturbation algorithms; major advances in scheduling capabilities; the prototype ISF (industrial Space Facility) experiment scheduler; optimized schedule (max revenue); multi-variable optimization; Space Station design reference mission scheduling; ISF-TDRSS command scheduling demonstration; and example task - communications check.

Kurtzman, Clifford R.↗
DOE OSTI2020

K-Spin Hamiltonian for Quantum-Resolvable Markov Decision Processes

The Markov decision process is the mathematical formalization underlying the modern field of reinforcement learning when transition and reward functions are unknown. We derive a pseudo-Boolean cost function that is equivalent to a K-spin Hamiltonian representation of the discrete, finite, discounted Markov decision process with infinite horizon. This K-spin Hamiltonian furnishes a starting point from which to solve for an optimal policy using heuristic quantum algorithms such as adiabatic quantum annealing and the quantum approximate optimization algorithm on near-term quantum hardware. In arguing that the variational minimization of our Hamiltonian is approximately equivalent to the Bellman optimality condition for a prevalent class of environments we establish an interesting analogy with classical field theory. Along with proof-of-concept calculations to corroborate our formulation by simulated and quantum annealing against classical Q-Learning, we analyze the scaling of physical resources required to solve our Hamiltonian on quantum hardware.

Hamiltonian↗
DOE OSTI2019

Lagrangian relaxation based heuristics for a chance-constrained optimization model of a hybrid solar-battery storage system

Here, we develop a stochastic optimization model for scheduling a hybrid solar-battery storage system. Solar power in excess of the promise can be used to charge the battery, while power short of the promise is met by discharging the battery. We ensure reliable operations by using a joint chance constraint. Models with a few hundred scenarios are relatively tractable; for larger models, we demonstrate how a Lagrangian relaxation scheme provides improved results. To further accelerate the Lagrangian scheme, we embed the progressive hedging algorithm within the subgradient iterations of the Lagrangian relaxation. Lastly, we investigate several enhancements of the progressive hedging algorithm, and find bundling of scenarios results in the best bounds.

14 SOLAR ENERGY↗
DOE OSTI2026

A Hierarchical Optimization Method for Electric Vertical Takeoff and Landing Aircraft Network Design

Electric vertical takeoff and landing aircraft (eVTOLs) are expected to serve urban air mobility in a station-to-station configuration, which makes the optimal network design of eVTOL stations a critical question to explore. Existing approaches often face limitations, such as the inability to interact station locations with demand or difficulty in finding the optimal solution for large study regions. Here, this paper first proposes a mathematical model to generate optimal eVTOL station locations while considering associated potential eVTOL demand, and then proposes a heuristic algorithm, Hierarchical Optimization MEthod (HOME), to efficiently solve the model. With a case study of Southern California, HOME was compared to 1) directly solving the original integer linear programming-based network design problem, and 2) employing the widely used genetic algorithm. Results suggest that HOME can find optimal solutions with limited computational resources. The proposed framework powered by HOME provides a computationally efficient way to support urban air mobility planning.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Light Water Reactor LEU+ Lattice Optimization

Commercial light water reactor (LWR) operators and fuel vendors in the United States are exploring potential changes to nuclear fuel that include low-enriched uranium plus (LEU+) designs to further improve operational economics (e.g., extend cycle length). LEU+ fuel is fuel with a maximum enrichment between 5 wt% and 10 wt% 235 U; it allows for higher assembly burnup but likely requires additional reactivity control, e.g., increased burnable absorbers. This report examines possible LEU+ fuel lattice design changes using the lattice physics code, SCALE/Polaris. An optimization driver called the Metaheuristic Optimization Tool (MOT) is used to automate domain space exploration and optimization of LEU+ lattice designs. Heuristics from previous LWR lattice optimization studies were used to construct the objective function and define the domain space for optimization. This work successfully demonstrated that the optimization algorithms of MOT can generate feasible, nonproprietary LEU+ lattice designs (GE14 10 × 10 and Westinghouse 17 × 17) that meet the constraints of traditional LWR lattices while extending cycle length.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2018

Distributed Louvain Algorithm for Graph Community Detection

In most real-world networks, the nodes/vertices tend to be organized into tightly-knit modules known as communities or clusters, such that nodes within a community are more likely to be “related” to one another than they are to the rest of the network. The goodness of partitioning into communities is typically measured using a well known measure called modularity. However, modularity optimization is an NP-complete problem. In 2008, Blondel, et al. introduced a multi-phase, iterative heuristic for modularity optimization, called the Louvain method. Owing to its speed and ability to yield high quality communities, the Louvain method continues to be one of the most widely used tools for serial community detection. In this paper, we present the design of a distributed memory implementation of the Louvain algorithm for parallel community detection. Our approach begins with an arbitrarily partitioned distributed graph input, and employs several heuristics to speedup the computation of the different steps of the Louvain algorithm. We evaluate our implementation and its different variants using real-world networks from various application domains (including internet, biology, social networks). Our MPI+OpenMP implementation yields about 7x speedup (on 4K processes) for soc-friendster network (1.8B edges) over a state-of-the-art shared-memory multicore implementation (on 64 threads), without compromising output quality. Furthermore, our distributed implementation was able to process a larger graph (uk-2007; 3.3B edges) in 32 seconds on 1K cores (64 nodes) of NERSC Cori, when the state-of-the-art shared-memory implementation failed to run due to insufficient memory on a single Cori node containing 128 GB.

High performance computing, graph algorithms, Dist↗
NASA NTRS2018

XY vs X Mixer in Quantum Alternating Operator Ansatz for Optimization Problems with Constraints

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

quantum computing↗
NASA NTRS2003

Iterative pass optimization of sequence data

The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

NASA Discipline Evolutionary Biology↗
NASA NTRS1975

Optimization of system reliability by the sequential unconstrained minimization technique

The reliability of a complex system was optimized by a new approach for implementing the sequential unconstrained minimization technique (SUMT) with the aid of Hooke and Jeeves pattern search and heuristic programming. Two optimization problems were considered. In the first, the system reliability was maximized subject to a nonlinear weight constraint. In the second, the weight of the system was minimized without violating the requirements of the minimal system reliability and the minimum reliability for each component. The sensitivities of the system reliability and that of the system weight to the reliability of each component were determined under optimal conditions.

Hwang, C. L.↗
DOE OSTI2024

Semiglobal Safety-Filtered Extremum Seeking With Unknown CBFs

We introduce a safe extremum-seeking (Safe ES) algorithm which achieves the minimization of an unknown objective function while ensuring that an unknown, yet measured, control barrier function (CBF) remains above an arbitrarily small negative value for all time. In other words, “practical safety” is maintained during the entire period of convergence to the constrained extremum. Our design is based on quadratic program (QP) CBF style filters for safety, which is applied in an average and estimated sense. Using nonsmooth analysis tools, we guarantee semiglobal practical asymptotic (SPA) stability of the global constrained optimum, practical convergence to the safe set if starting in a condition violating the CBF, and practical safety for all time—semiglobally—if starting in safe set. The safety result of the paper is analogous with modern notions of SPA stability, guaranteeing that, for any small violation of safety, there exist design coefficients which guarantee that such a small violation is not exceeded. The paper outlines a set of sufficient conditions on the barrier and objective functions, and by way of a Lyapunov argument, we demonstrate that nonconvex constrained optimization problems can be solved. We present these results in the setting of a static map and a dynamical system. A simulation example illustrates the results.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Ensuring reliable connectivity to cellular-connected UAVs with up-tilted antennas and interference coordination

To integrate unmanned aerial vehicles (UAVs) in future large-scale deployments, a new wireless communication paradigm, namely, the cellular-connected UAV has recently attracted interest. However, the line-of-sight dominant air-to-ground channels along with the antenna pattern of the cellular ground base stations (GBSs) introduce critical interference issues in cellular-connected UAV communications. In particular, the complex antenna pattern and the ground reflection (GR) from the down-tilted antennas create both coverage holes and patchy coverage for the UAVs in the sky, which leads to unreliable connectivity from the underlying cellular network. To overcome these challenges, in this paper, we propose a new cellular architecture that employs an extra set of co-channel antennas oriented towards the sky to support UAVs on top of the existing down-tilted antennas for ground user equipment (GUE). To model the GR stemming from the down-tilted antennas, we propose a path-loss model, which takes both antenna radiation pattern and configuration into account. Next, we formulate an optimization problem to maximize the minimum signal-to-interference ratio (SIR) of the UAVs by tuning the up-tilt (UT) angles of the up-tilted antennas. Since this is an NP-hard problem, we propose a genetic algorithm (GA) based heuristic method to optimize the UT angles of these antennas. After obtaining the optimal UT angles, we integrate the 3GPP Release-10 specified enhanced inter-cell interference coordination (eICIC) to reduce the interference stemming from the down-tilted antennas. Our simulation results based on the hexagonal cell layout show that the proposed interference mitigation method can ensure higher minimum SIRs for the UAVs over baseline methods while creating minimal impact on the SIR of GUEs.

3GPP↗
DOE OSTI2024

OPER: Optimality-Guided Embedding Table Parallelization for Large-scale Recommendation Model

With the sharp increasing volume of user data, Deep Learning Recommendation Model (DLRM) becomes an indispensable infrastructure in large technology companies. However, large-scale DLRM on the multi-GPU platform is still inefficient due to unbalanced workload partitioning and intensive inter-GPU communication. To this end, we propose OPER, an OPtimality guided Embedding table placement for large-scale Recommendation model training and inference. OPER explores the potential of mitigating remote memory access latency in DLRM through fine-grained embedding table placement. Specifically, OPER proposes a theoretical modeling that builds up the relationship between EMT placement and the embedding communication latency in both training and inference. OPER proves the NP hardness of finding the optimal embedding table placement and proposes a heuristic algorithm that yields near optimal placement. OPER implements a SHMEM-based embedding table training system and a unified embedding index mapping to support fine-grained embedding table sharding and placement. Comprehensive experiments reveal that OPER achieves on average 3.4× and 5.1× speedup on training and inference respectively over state-of-the-art DLRM frameworks.

Wang, Zheng↗
DOE OSTI2019

Optimization of Structural Flood Mitigation Strategies

The dynamics of flooding are primarily influenced by the shape, height, and roughness (friction) of the underlying topography. For this reason, mechanisms to mitigate floods frequently employ structural measures that either modify topographic elevation, for example, through the placement of levees and sandbags, or increase roughness, for example, through revegetation projects. However, the configuration of these measures is typically decided in an ad hoc manner, limiting their overall effectiveness. The advent of high–performance surface–water modeling software and improvements in black–box optimization suggest that a more principled design methodology may be possible. This paper proposes a new computational approach to the problem of designing structural mitigation strategies under physical and budgetary constraints. It presents the development of a problem discretization amenable to simulation–based, derivative–free optimization. However, meta–heuristics alone are found to be insufficient for obtaining quality solutions in a reasonable amount of time. As a result, this paper proposes novel numerical and physics–based procedures to improve convergence to a high–quality mitigation. Furthermore the efficiency of the approach is demonstrated on hypothetical dam break scenarios of varying complexity under various mitigation budget constraints. In particular, experimental results show that, on average, the final proposed algorithm results in a 65% improvement in solution quality compared to a direct implementation.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2023

Application of step-response lambda tuning to proportional-integral controllers in water resource recovery facilities

Proportional-integral-derivative (PID) controllers in water resource recovery facilities (WRRFs) feedback control loops are commonplace. While simple to implement, such control loops are rarely tuned optimally or systematically. Heuristic tuning approaches are commonly applied with varying degrees of success using trial-and-error, ad hoc tuning rules, or duplication of tuning values from a similar system. However, there are effective methods, such as lambda tuning, produce acceptable tuning with limited effort. These are based on the step-response method, where a manual process perturbation is used to define the relationship between the manipulated and controlled variables. Based on such an experiment, a simple process model is constructed and used to determine the controller tuning values. In this work, we used the step-response method and lambda tuning for two control systems in full-scale WRRFs. This led to responsive and stable behavior of the controlled system as defined by the absolute average error of the controlled variable to setpoint and standard deviation of the manipulated variable. Tuning of feedback control loops can be completed successfully through a systematic approach, and this work suggests that tuning tools, like lambda, should be part of all wastewater treatment control engineers' toolbox.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2019

Evaluation of Hydrogen Production Feasibility for a Light Water Reactor in the Midwest

Increased electricity production from renewable energy resources coupled with low natural gas prices has caused existing light-water reactor (LWRs) to experience ever diminishing returns from the electricity market. Via partnership among Idaho National Laboratory (INL), The National Renewable Energy Laboratory (NREL), Argonne National Laboratory (ANL), Exelon, and Fuel Cell Energy a techno-economic analysis on the viability of retrofitting existing pressurized water reactors (PWRs) to produce hydrogen (H2) via high temperature steam electrolysis (HTSE) has been conducted. Such integration would allow nuclear facilities to expand into additional markets that may be more profitable in the long-term. To accommodate such an integration, a detailed analysis of HTSE process operation, requirements, and flexibility was conducted. Technical analysis includes proposed nuclear system control scheme modifications to allow dynamic operation of the HTSE via both thermal and electrical connection to the nuclear plant. High fidelity Modelica simulations showcase the viability of such control schemes. However, due to limited knowledge of solid oxide fuel cell (SOFC) stack degradation due to thermal gradients; thermal cycling of the HTSE was not included. Therefore, the control schemes proposed are only utilized to re-distribute steam at startup and only the portion of electricity utilized in the electrolyzers is cycled. From the detailed analysis of the nuclear integration and the HTSE process design, a comprehensive cost estimation was conducted in the APEA and H2A models to elucidate capital and operational costs associated with the production, compression, and distribution of hydrogen from a nuclear facility. Alongside this costing analysis, market analyses were conducted by NREL and ANL on the electric and hydrogen markets respectively in the PJM interconnect. Utilizing the electricity data market projections in the PJM interconnect from NREL and hydrogen demand/pricing projections from ANL a five variable sweep over component capacities, discount rates, and hydrogen pricing was completed using the stochastic framework RAVEN (Risk Analysis Virtual ENVironment) through its resource dispatch plugin HERON (Heuristic Energy Resource Optimization Network). Each combination of variables was evaluated stochastically four times over a seventeen year timespan from 2026-2042 (inclusive) to determine the most economically advantageous solution. Following the five variable sweep an optimization was conducted about the best sweep point to determine optimal component sizing and setpoints. Results suggest positive gain is achievable at all projected hydrogen market pricing levels and at all discount rates. However, exact component sizing and net returns vary based on these values and if incorrect sizing is selected; major net losses can occur. The optimal result occurred with set points as follows: high hydrogen prices, the largest possible HTSE unit in the sweep set at 7.47 kg/sec [645.4 tpd], a contractual hydrogen market agreement 7.29 kg/sec [629.8 tpd], and a hydrogen storage size 115,188 kg. The analysis suggested that with a discount rate of 8%, a ΔNPV = 1.2 billion over the seventeen year span can be achieved. The results illuminate that by operating in multiple markets the nuclear facility is capable of avoiding sale of electricity during times of low electricity market pricing, while maintaining the ability to capitalize on the high electricity market pricing. It should be noted that the analysis conducted in this report is a differential cash flow analysis and as such does not present profit levels. Instead it highlights the net benefit between building and competing in the hydrogen market utilizing nuclear facilities and conducting business as usual in the electricity markets. Additionally, results presented in this report exhibit conservatism due to four key assumptions: Given the limited knowledge on SOFC stack degradation due to thermal gradients the high temperature steam electrolysis plant is not allowed to thermally cycle. This limitation decreases electricity generation capacity in the nuclear plant, reducing capacity payments and the maximum output to the electrical grid. This analysis considers building a separate hydrogen pipeline for use in the nuclear facility. Research is currently being conducted to determine if existing natural gas pipelines can accommodate direct hydrogen injection. If hydrogen can be integrated into existing natural gas pipelines then a capital savings of ~$19,000,000 per kg/sec [1 kg/sec = 86.4 tpd] of installed HTSE capacity could be realized. Fast transients in the electric grid are typically served by flywheels and electric batteries. With electrolysis only operation the nuclear plant can flex its electricity just as quickly. However, for this analysis, the ancillary services market has been neglected. Should the nuclear plant have the ability to operate in the ancillary services market during periods when it is producing hydrogen, an additional substantial income stream that would increase overall system profitability could be considered. Subsidies for non-emitting generation technologies are not introduced in the cash flow analysis, but instead are completed assuming zero subsidies. Profitability is based solely on electricity pricing. Electric pricing is assumed to never go negative. Instead, it is assumed overall system curtailment by the Independent System Operator (ISO) will occur in such a manner that pricing remains at or above zero. This assumption inflates the “business as usual” scenario, thus decreasing the ΔNPV calculated. If negative pricing scenarios continue to occur as they do today, one would expect a further increase in ΔNPV. Overall, results advocate that, through market diversification, nuclear power plants have the potential to substantially increase current profit margins, increase market penetration, and ultimately solidify their place as a mainstay in energy production.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2020

Evaluation of Hybrid FPOG Applications in Regulated and Deregulated Markets Using HERON

Recent changes in the U.S. energy market, such as low natural gas prices and increased electricity production for variable renewable energy (VRE) sources, have led to an economic crisis for existing light-water reactor (LWR) nuclear power plants (NPP). Many owners and operators of LWRs have elected to decommission these plants rather than continue using them as consistent sources of clean baseload power. This has led to exploration of various possibilities to increase the economic viability of these units, including market restructuring to monetize benefits LWRs already provide to the grid through ancillary markets, load following and economic dispatch, and possible integration of secondary systems directly to the NPP for production of additional products through technologies such as hydrogen electrolysis or water desalination. Previous studies have considered the technologies associated with these Integrated Energy Systems (IES) activities, and the analysis of markets for these secondary products. To analyze the economic viability of various system configurations including IES, especially given the uncertainty surrounding load demand, electricity prices, and the availability of VRE resources, the stochastic technoeconomic analysis package HERON (Heuristic Energy Resource Optimization Network) was released earlier this year as an extension of the risk analysis framework RAVEN (Risk Analysis Virtual Environment). HERON focuses foremost on making the complex uncertainty quantification analysis tools approachable for energy systems analysts, also providing general dispatch optimization algorithms for those workflows. HERON continues to be improved and tested as a significant part of the IES viability analyses performed in this work. HERON is not a capacity expansion model. To consider market and grid energy system development in a variety of scenarios, HERON is best used in coupling with modelling tools such as US-REGEN, which sacrifice some of the uncertainty analysis and resolution of HERON's modelling for the ability to efficiently predict the change in the grid energy system's profile due to economic drivers over decades. HERON can then use this information to explore the economic viability of introducing changes to the predicted outcomes, such as the introduction of an IES. In this work, experts at EPRI using US-REGEN provide six projection scenarios for use in HERON stochastic technoeconomic analysis (STEA) in considering the options available for increasing LWR economic viability through introduction of a hydrogen-centric IES using a high-temperature steam electrolysis plant (HTSE), hydrogen storage, and a constant-rate contracted hydrogen consumer. The results obtained are differential in nature; they do not report expected profits for any configuration, but rather report on the possible increase in the NPV of a configuration with respect to a baseline no-IES configuration. Due to the uncertainty captured in the variable net load of the systems, there is likewise uncertainty in the mean values reported. We consider this viability both in terms of a regulated market, where the energy producers and IES are owned and operated by single entity, as well as a deregulated market, where the IES chooses its bid for electricity generation and is then dispatched by the grid system operator. Results indicate that for deregulated markets, the inclusion of the IES is often statistically beneficial. This is especially true in policies that are not favorable towards nuclear, as nuclear is less often dispatched and is forced to deal with frequent idle capacity. In the nominal case as well as the case of carbon tax policies, inclusion of the IES clearly benefited the economic performance of the NPP. In the regulated case, however, there was a trend towards minimizing the IES, likely due to the optimal sizing performed by US-REGEN of the NPP within the system as well as the lack of penalty for idle capacity at the NPP in the regulated market analyses.

99 GENERAL AND MISCELLANEOUS↗
NASA NTRS1989

A two-phase methodology for technology selection and system design

A two-phase methodology that can be used to guide R&D managers in the evaluation and selection of competing technologies is presented. Deterministic multiattribute utility theory is used in the first phase to rank the technological alternatives; the example presented involves the evaluation of electric and hybrid passenger vehicles. In all, 39 individuals from eight automotive firms were interviewed to assess their risk preferences and attitudes toward the vehicle design. In the second phase, the decision-maker must allocate a fixed amount of resources to different projects for the technology selected, some of which may be undertaken in parallel, to maximize a given measure of performance. When parallel funding is pursued the best outcome is chosen. The problem is formulated as a probabilistic network and solved heuristically using Monte Carlo simulation. Results are presented for two decision-makers and three budget options. In each case, the heuristic finds the optimal allocation of funds.

Bard, Jonathan F.↗