Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Heuristic algorithms”

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 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Finding diverse ways to improve algebraic connectivity through multi-start optimization

The algebraic connectivity, also known as the Fiedler value, is a spectral measure of network connectivity that can be increased through edge addition. We present an algorithm for producing many diverse ways to add a fixed number of edges to a network to achieve a near optimal Fiedler value. Previous Fielder value optimization algorithms (i.e. the greedy algorithm) output only one solution. Obtaining a single solution is rarely good enough for real-world network redesign problems, as practical constraints (political, physical or financial) may prevent implementation. Our algorithm takes a multi-start optimization approach, adding a random initial edge and then applies a greedy heuristic to improve the Fiedler value. The random choice moves us to a new region of the search space, enabling discovery of diverse solutions. Additionally, we present a Determinantal Point Process framework for quantifying diversity. We then apply a Markov chain Monte Carlo technique to sift through the large number of output solutions and locate a smaller, more manageable collection of highly diverse solutions that can be presented to network redesign engineers. We demonstrate the effectiveness of our algorithm on real-world graphs with varied structures.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Quantum annealing algorithms for Boolean tensor networks

Abstract Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., $$\{0, 1\}$$ { 0 , 1 } ) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor’s with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

CoSHA: Code for Stellar Properties Heuristic Assignment—for the MaStar Stellar Library

We introduce CoSHA: a Code for Stellar properties Heuristic Assignment. In order to estimate the stellar properties, CoSHA implements a Gradient Tree Boosting algorithm to label each star across the parameter space (T eff , $\mathrm{log}g$, [Fe/H], and [α/Fe]). We use CoSHA to estimate the stellar atmospheric parameters of 22,000 unique stars in the MaNGA Stellar Library (MaStar). To quantify the reliability of our approach, we run internal tests, using both the Göttingen Stellar Library (a theoretical library) and the first data release of MaStar, and external tests, by comparing the resulting distributions in the parameter space with the APOGEE estimates of the same properties. In summary, our parameter estimates span the ranges T eff = [2900, 12,000] K, $\mathrm{log}g=[-0.5,5.6]$, [Fe/H] = [-3.74, 0.81], and αM = [-0.22, 1.17]. We report internal (external) uncertainties of the properties of ${\sigma }_{{T}_{\mathrm{eff}}}\sim 43(240)$ K, ${\sigma }_{\mathrm{log}g}\sim 0.2(0.4)$, σ [Fe/H] ~ 0.16(0.24), and σ [α/Fe] ~ 0.09(0.08). These uncertainties are comparable to those of other methods with similar objectives. Despite the fact that CoSHA is not aware of the spatial distributions of these physical properties in the Milky Way, we are able to recover the main trends known in the literature. The catalog of physical properties for MaStar can be accessed online.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2024

Solving the Grid Optimization Competition Challenge 3 Problem

The Grid Optimization Competition Challenge 3 Problem posed a multiperiod security-constrained unit commitment problem with base-case AC power flow. The problem formulation includes binary unit commitment decisions, nonlinear AC power flow and balance, dispatchable loads, and linearized contingency real power flow, among other features. This talk will present a modified consensus ADMM algorithm, which splits the problem into mixed-integer linear and nonlinear components, as a heuristic solution method for this large-scale mixed integer nonlinear program. We will present some computational results from the competition for our implementation and reflect on the challenges of participating the grid optimization competition.

AC power flow↗
DOE OSTI2023

Code for Value Decomposition Graph Network and environment for AMR on linear advection

This is the code for the paper [Multi-Agent Reinforcement Learning for Adaptive Mesh Refinement](https://arxiv.org/abs/2211.00801), published at AAMAS 2023. It contains the implementation of a new algorithm, called Value Decomposition Graph Network (VDGN), for applying multi-agent reinforcement learning to the problem of adaptive mesh refinement (AMR). It also contains the implementation of a multi-agent environment for AMR on a linear advection problem. VDGN is the first learning algorithm to display anticipatory refinement behavior in AMR, and it outperforms local error threshold-based heuristic strategies.

Yang, Jiachen↗
DOE OSTI2022

Numerical gate synthesis for quantum heuristics on bosonic quantum processors

There is a recent surge of interest and insights regarding the interplay of quantum optimal control and variational quantum algorithms. We study the framework in the context of qudits which are, for instance, definable as controllable electromagnetic modes of a superconducting cavity system coupled to a transmon. By employing recent quantum optimal control approaches described in (Petersson and Garcia, 2021), we showcase control of single-qudit operations up to eight states, and two-qutrit operations, mapped respectively onto a single mode and two modes of the resonator. We discuss the results of numerical pulse engineering on the closed system for parametrized gates useful to implement Quantum Approximate Optimization Algorithm (QAOA) for qudits. The results show that high fidelity ( > 0.99) is achievable with sufficient computational effort for most cases under study, and extensions to multiple modes and open, noisy systems are possible. The tailored pulses can be stored and used as calibrated primitives for a future compiler in circuit quantum electrodynamics (cQED) systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

The LSBmax algorithm for boosting resilience of electric grids post (N‐2) contingencies

Abstract A computationally improved algorithm is presented to find the best transmission switching (TS) candidate for boosting resilience of electricity grids subject to ( N ‐2) contingencies. Here, resilience is computed as the reduction in load shed after the above‐mentioned ( N‐ ) contingencies. TS is a planned line outage, and past research shows that changing the transmission system's topology changes the power flow and removes post contingency violations. Finding the best TS candidate in a computationally suitable time for effectively boosting resilience is a challenge. The best TS candidate is found using a novel heuristic method by decreasing the search space based on proximity to the bus with the maximum load shedding (LSB). The LSB algorithm is faster than existing algorithms in the literature; and, it is compatible with both the AC and DC optimal power flow formulations. To validate the authors' claims of speedup and accuracy, two metrics are used to analyze the results from the IEEE 39‐bus and 118‐bus systems. Finally, the inherent parallelism of the LSB algorithm is leveraged on a high‐performance computing platform and applied to the large‐scale Polish 2383‐bus test system to validate scalability in both size and speedup in computation time.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

An Orthogonal Recursive Bisection (ORB) Based Time Advancement Algorithm for CFD-DEM Solvers

The time integration of the granular phase in coupled computational fluid dynamics (CFD) – discrete element method (DEM) simulations presents a unique computational challenge brought about by the large variations in particle collisional time scales. Particles in the dilute regions of the computational domain can be advanced with large time steps while dense regions require much smaller time increments. However, the time step size in most solvers is globally set as the limit for accuracy and stability imposed by the collisions and is typically orders of magnitude less than that required away from collisions. This work addresses this precise issue and provides a strategy to avoid the use of a global conservative small time step size for the entire set of particles.A novel time stepping algorithm for CFD-DEM solvers using a partitioning approach using orthogonal recursive bisection (ORB) that allows for variable time steps among particles is described and its computational performance is compared against baseline explicit methods, typically used in several CFD-DEM solvers. ORB has advantages of being relatively quick and easy to update incrementally and has the required heuristic behavior (i.e., it will split the region in half with a cluster on each side) when groups of particles are well separated (clustered). The algorithm presented in this work uses a local time stepping approach to resolve collisional time scales for subsets of particles that are present at the leaves of the ORB, thereby resulting in substantial reduction of computational cost. The parallel implementation of this method where a ``knapsack” algorithm is used in tandem with ORB for effective load-balancing is also presented, where a best possible partitioning is obtained based on number of particles and local time-stepping costs. The algorithm is tested against benchmark problems with varying particle distributions that include fluidized bed and riser flow scenarios. Preliminary results indicate that the approach is 2-3X faster than traditional explicit methods for problems that involve both dense and dilute regions, while maintaining the same level of accuracy.

adaptive timestepping↗
DOE OSTI2022

A Reinforcement Learning Approach to Parameter Selection for Distributed Optimal Power Flow

With the increasing penetration of distributed energy resources, distributed optimization algorithms have attracted significant attention for power systems applications due to their potential for superior scalability, privacy, and robustness to a single point-of-failure. The Alternating Direction Method of Multipliers (ADMM) is a popular distributed optimization algorithm; however, its convergence performance is highly dependent on the selection of penalty parameters, which are usually chosen heuristically. In this work, we use reinforcement learning (RL) to develop an adaptive penalty parameter selection policy for alternating current optimal power flow (ACOPF) problem solved via ADMM with the goal of minimizing the number of iterations until convergence. We train our RL policy using deep Q-learning and show that this policy can result in significantly accelerated convergence (up to a 59% reduction in the number of iterations compared to existing, curvatureinformed penalty parameter selection methods). Furthermore, we show that our RL policy demonstrates promise for generalizability, performing well under unseen loading schemes as well as under unseen losses of lines and generators (up to a 50% reduction in iterations). This work thus provides a proof-of-concept for using RL for parameter selection in ADMM for power systems applications.

alternating current optimal power flow↗
DOE OSTI2023

A parallel variable population multi-objective optimizer for accelerator beam dynamics optimization

The simultaneous optimization of multiple objective functions is needed in many particle accelerator applications. In this paper, we present a parallel evolution based multi-objective optimizer that uses a variable population from generation to generation and an external storage to save good solutions. Two heuristic optimization methods, one uses the unified differential evolution and the other uses the real-coded genetic algorithm, are included in the optimizer to generate next generation candidate solutions, and are compared in the test examples. Finally, as an application, we applied this optimizer to the beam dynamics design optimization of a photoinjector and attained the optimal front solutions after 200 generations with the unified differential evolution offspring production scheme.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

Quantum Optimization: Potential, Challenges, and the Path Forward

Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains. Across computer science and physics, there are a number of algorithmic approaches, often with little linkage. This is further complicated by the fragmented nature of the field of mathematical optimization, where major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions, have devoted communities. With these aspects in mind, this work draws on multiple approaches to study quantum optimization. Provably exact versus heuristic settings are first explained using computational complexity theory — highlighting where quantum advantage is possible in each context. Then, the core building blocks for quantum optimization algorithms are outlined to subsequently define prominent problem classes and identify key open questions that, if answered, will advance the field. The effects of scaling relevant problems on noisy quantum devices are also outlined in detail, alongside meaningful benchmarking problems. We underscore the importance of benchmarking by proposing clear metrics to conduct appropriate comparisons with classical optimization techniques. Lastly, we highlight two domains – finance and sustainability – as rich sources of optimization problems that could be used to benchmark, and eventually validate, the potential real-world impact of quantum optimization.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Toward a machine-guided approach to energetic material discovery

In this article, we trained a machine learning (ML) model to connect microstructural details of an energetic material formulation to its performance for the purpose of guiding the discovery of new explosive formulations. Our hypothesis was that the algorithm would robustly learn the training data and produce an accurate surrogate model. Specifically, the algorithm learned the relationship between details of the void size distribution (VSD), initiating shock pressure, and the energetic material performance. We used realistic constraints on the VSD and a range of cases were ingested by a physically informed reactive flow model working within a hydrodynamic solver running on high-performance computing resources. The ML algorithm produced a surrogate model that accurately predicted known test points around the parameter space. In addition to the utility of the model and the process used for its development, we noted interesting comparisons between what we, the authors—subject matter experts, would heuristically conclude from the training data and the surrogate model predictions. We detected nuanced details that were missed by the surrogate model; however, these details are not important to an energetic material formulator. We concluded that the algorithm did indeed robustly learn the training data and produce an accurate surrogate model. We further concluded that the surrogate model is a powerful tool to guide the formulator in the absence of subject matter experts and limited-access computing resources.

42 ENGINEERING↗
DOE OSTI2026

Full event interpretation with machine-learning-based particle-flow reconstruction in the CMS detector

The particle-flow (PF) algorithm constructs a global description of each particle collision by producing a comprehensive list of final-state particles, and is central to event reconstruction in the CMS experiment at the CERN LHC. The existing PF implementation relies on physics-motivated heuristics and assumptions that can be replaced by machine-learning (ML) models trained directly on simulated data and naturally suited to modern graphics processing units (GPUs). A state-of-the-art ML-based PF (MLPF) reconstruction algorithm, implemented within the CMS software framework, is presented. The MLPF algorithm performs a learnable full-event reconstruction on GPUs, generalizes across detector conditions and collision energies, and replaces multiple modular reconstruction steps with a single unified model. Physics performance comparable to standard PF reconstruction is achieved in both simulation and data, with improved jet energy resolution and inference time. In simulated top quark-antiquark events under LHC Run-3 (2023-2024) conditions, the jet energy resolution improves by 10-20% for jets with transverse momentum between 30-100 GeV. Inference time is evaluated using simulated multijet events, with a median of $20\,\hbox {ms}$ per event on an Nvidia L4 GPU, compared to approximately $110\,\hbox {ms}$ for the standard CMS PF reconstruction.

Hayrapetyan, Aram [Yerevan Phys. Inst.]↗
DOE OSTI2024

Enhancing molecular design efficiency: Uniting language models and generative networks with genetic algorithms

This study examines the effectiveness of generative models in drug discovery, material science, and polymer science, aiming to overcome constraints associated with traditional inverse design methods relying on heuristic rules. Generative models generate synthetic data resembling real data, enabling deep learning model training without extensive labeled datasets. They prove valuable in creating virtual libraries of molecules for material science and facilitating drug discovery by generating molecules with specific properties. While generative adversarial networks (GANs) are explored for these purposes, mode collapse restricts their efficacy, limiting novel structure variability. To address this, we introduce a masked language model (LM) inspired by natural language processing. Although LMs alone can have inherent limitations, we propose a hybrid architecture combining LMs and GANs to efficiently generate new molecules, demonstrating superior performance over standalone masked LMs, particularly for smaller population sizes. This hybrid LM-GAN architecture enhances efficiency in optimizing properties and generating novel samples.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

A Flexible Forwarding Scheme to Improve Latency-Bound Irregular P2P Communication in MPI

We propose an algorithm to efficiently perform latency-bound communication scenarios that consist of many small messages. In these parallel scenarios, processes typically pass around a lot of small-sized messages of a few KBs of size. Performing communication operations with P2P MPI routines or collective MPI routines (including neighborhood collectives) in such scenarios may not always yield the optimal results and may not resolve the latency bottleneck. To this end, we develop a regular structure called virtual process topology (VPT) on which the messages can be communicated in a structured and controlled manner. Using parameters of this topology, one can tune the rate of aggression in tackling the latency costs. We demonstrate that our communication algorithm is preferable to MPI P2P and collective routines for latency-bound communication and it can easily be adapted only by replacing calls to MPI routines in a parallel application. We show how to adapt existing topology-aware mapping heuristics to address the volume overhead due to communicating messages on the VPT. Moreover, we propose a novel swap-based mapping heuristic to address this overhead by optimizing the maximum volume handled by a process. Experiments on synthetic communication graphs as well as real-world applications such as parallel Canonical Polyadic sparse tensor decomposition and parallel sparse matrix-dense matrix multiplication show that our approach is a powerful way of overcoming the bottlenecks posed by sparse and latency-bound irregular communication.

communication algorithm↗
DOE OSTI2024

Tensor decompositions for count data that leverage stochastic and deterministic optimization

There is growing interest to extend low-rank matrix decompositions to multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is the canonical polyadic decomposition (CPD). The challenge of fitting a low-rank, nonnegative CPD model to Poisson-distributed count data is of particular interest. Several popular algorithms use local search methods to approximate the maximum likelihood estimator (MLE) of the Poisson CPD model. Here, this work presents two new algorithms that extend state-of-the-art local methods for Poisson CPD. Hybrid GCP-CPAPR combines Generalized Canonical Decomposition (GCP) with stochastic optimization and CP Alternating Poisson Regression (CPAPR), a deterministic algorithm, to increase the probability of converging to the MLE over either method used alone. Restarted CPAPR with SVDrop uses a heuristic based on the singular values of the CPD model unfoldings to identify convergence toward optimizers that are not the MLE and restarts within the feasible domain of the optimization problem, thus reducing overall computational cost when using a multi-start strategy. We provide empirical evidence that indicates our approaches outperform existing methods with respect to converging to the Poisson CPD MLE.

CPAPR↗
DOE OSTI2023

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2026

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗