Search NASA⌕ Search

SEARCH · Search NASA

Results for “Combinatorial 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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Scaling quantum approximate optimization on near-term hardware

The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

TCF High Efficiency Anaerobic Electroporation (CRADA Final Report)

The Joint BioEnergy Institute (JBEI) researchers were co-inventors of the technology that will be used on this project and have developed a more current version of the chip and controller. JBEI will also assist with the design of the pathways and implementation of pathways on the chip. LanzaTech has developed novel gas fermentation technology that captures and utilizes greenhouse gases for production of fuels and chemicals. In contrast to traditional fermentation that uses sugars as substrate (and releases CO2 as a byproduct), gas fermentation utilizes C1 substrates carbon monoxide (CO) or CO2. This enables a diverse range of feedstock options including waste gases from industrial sources (e.g., steel mills and processing plants) or syngas generated from any biomass resource (e.g., agricultural waste, municipal solid waste, or organic industrial waste). Biomass is then gasified, allowing for maximum yields and complete carbon utilization including the recalcitrant lignocellulosic fraction that cannot be utilized in traditional sugar fermentation. To maximize the value that can be added to the array of gas resources that the LanzaTech process can use as an input, LanzaTech has pioneered genetic modification of acetogens and developed a comprehensive set of genetic tools to perform routine strain modification, including genome editing tools as CRISPR/Cas9 and libraries of validated genetic parts as promoters and terminators. Using this platform, production of over 50 new molecules have been demonstrated directly from gas. For a few selected molecules production rates and yields have been optimized and surpass production of native producers and engineered E. coli or yeast strains, but a higher throughput approach for combinatorial optimization of pathways is required to further advance synthesis of additional products in parallel.

09 BIOMASS FUELS↗
NASA NTRS1999

Optimization Strategies for Sensor and Actuator Placement

This paper provides a survey of actuator and sensor placement problems from a wide range of engineering disciplines and a variety of applications. Combinatorial optimization methods are recommended as a means for identifying sets of actuators and sensors that maximize performance. Several sample applications from NASA Langley Research Center, such as active structural acoustic control, are covered in detail. Laboratory and flight tests of these applications indicate that actuator and sensor placement methods are effective and important. Lessons learned in solving these optimization problems can guide future research.

Padula, Sharon L.↗
DOE OSTI2025

Toward computing bounds for Ramsey numbers using quantum annealing

Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Relation Inference among Sensor Time Series in Smart Buildings with Metric Learning

Smart Building Technologies hold promise for better livability for residents and lower energy footprints. Yet, the rollout of these technologies, from demand response controls to fault detection and diagnosis, significantly lags behind and is impeded by the current practice of manual identification of sensing point relationships, e.g., how equipment is connected or which sensors are co-located in the same space. This manual process is still error-prone, albeit costly and laborious.We study relation inference among sensor time series. Our key insight is that, as equipment is connected or sensors co-locate in the same physical environment, they are affected by the same real-world events, e.g., a fan turning on or a person entering the room, thus exhibiting correlated changes in their time series data. To this end, we develop a deep metric learning solution that first converts the primitive sensor time series to the frequency domain, and then optimizes a representation of sensors that encodes their relations. Built upon the learned representation, our solution pinpoints the relationships among sensors via solving a combinatorial optimization problem. Extensive experiments on real-world buildings demonstrate the effectiveness of our solution.

96 KNOWLEDGE MANAGEMENT AND PRESERVATION↗
DOE OSTI2025

ON-OFF neuromorphic ISING machines using Fowler-Nordheim annealers

We introduce NeuroSA, a neuromorphic architecture specifically designed to ensure asymptotic convergence to the ground state of an Ising problem using a Fowler-Nordheim quantum mechanical tunneling based threshold-annealing process. The core component of NeuroSA consists of a pair of asynchronous ON-OFF neurons, which effectively map classical simulated annealing dynamics onto a network of integrate-and-fire neurons. The threshold of each ON-OFF neuron pair is adaptively adjusted by an FN annealer and the resulting spiking dynamics replicates the optimal escape mechanism and convergence of SA, particularly at low-temperatures. To validate the effectiveness of our neuromorphic Ising machine, we systematically solved benchmark combinatorial optimization problems such as MAX-CUT and Max Independent Set. Across multiple runs, NeuroSA consistently generates distribution of solutions that are concentrated around the state-of-the-art results (within 99%) or surpass the current state-of-the-art solutions for Max Independent Set benchmarks. Furthermore, NeuroSA is able to achieve these superior distributions without any graph-specific hyperparameter tuning. For practical illustration, we present results from an implementation of NeuroSA on the SpiNNaker2 platform, highlighting the feasibility of mapping our proposed architecture onto a standard neuromorphic accelerator platform.

42 ENGINEERING↗
NASA NTRS2002

Overall Traveling-Wave-Tube Efficiency Improved By Optimized Multistage Depressed Collector Design

Depressed Collector Design The microwave traveling wave tube (TWT) is used widely for space communications and high-power airborne transmitting sources. One of the most important features in designing a TWT is overall efficiency. Yet, overall TWT efficiency is strongly dependent on the efficiency of the electron beam collector, particularly for high values of collector efficiency. For these reasons, the NASA Glenn Research Center developed an optimization algorithm based on simulated annealing to quickly design highly efficient multistage depressed collectors (MDC's). Simulated annealing is a strategy for solving highly nonlinear combinatorial optimization problems. Its major advantage over other methods is its ability to avoid becoming trapped in local minima. Simulated annealing is based on an analogy to statistical thermodynamics, specifically the physical process of annealing: heating a material to a temperature that permits many atomic rearrangements and then cooling it carefully and slowly, until it freezes into a strong, minimum-energy crystalline structure. This minimum energy crystal corresponds to the optimal solution of a mathematical optimization problem. The TWT used as a baseline for optimization was the 32-GHz, 10-W, helical TWT developed for the Cassini mission to Saturn. The method of collector analysis and design used was a 2-1/2-dimensional computational procedure that employs two types of codes, a large signal analysis code and an electron trajectory code. The large signal analysis code produces the spatial, energetic, and temporal distributions of the spent beam entering the MDC. An electron trajectory code uses the resultant data to perform the actual collector analysis. The MDC was optimized for maximum MDC efficiency and minimum final kinetic energy of all collected electrons (to reduce heat transfer). The preceding figure shows the geometric and electrical configuration of an optimized collector with an efficiency of 93.8 percent. The results show the improvement in collector efficiency from 89.7 to 93.8 percent, resulting in an increase of three overall efficiency points. In addition, the time to design a highly efficient MDC was reduced from a month to a few days. All work was done in-house at Glenn for the High Rate Data Delivery Program. Future plans include optimizing the MDC and TWT interaction circuit in tandem to further improve overall TWT efficiency.

Vaden, Karl R.↗
NASA NTRS1996

Performance of Optimized Actuator and Sensor Arrays in an Active Noise Control System

Experiments have been conducted in NASA Langley's Acoustics and Dynamics Laboratory to determine the effectiveness of optimized actuator/sensor architectures and controller algorithms for active control of harmonic interior noise. Tests were conducted in a large scale fuselage model - a composite cylinder which simulates a commuter class aircraft fuselage with three sections of trim panel and a floor. Using an optimization technique based on the component transfer functions, combinations of 4 out of 8 piezoceramic actuators and 8 out of 462 microphone locations were evaluated against predicted performance. A combinatorial optimization technique called tabu search was employed to select the optimum transducer arrays. Three test frequencies represent the cases of a strong acoustic and strong structural response, a weak acoustic and strong structural response and a strong acoustic and weak structural response. Noise reduction was obtained using a Time Averaged/Gradient Descent (TAGD) controller. Results indicate that the optimization technique successfully predicted best and worst case performance. An enhancement of the TAGD control algorithm was also evaluated. The principal components of the actuator/sensor transfer functions were used in the PC-TAGD controller. The principal components are shown to be independent of each other while providing control as effective as the standard TAGD.

Palumbo, D. L.↗
NASA NTRS1996

Performance of Optimized Actuator and Sensor Arrays in an Active Noise Control System

Experiments have been conducted in NASA Langley s Acoustics and Dynamics Laboratory to determine the effectiveness of optimized actuator/sensor architectures and controller algorithms for active control of harmonic interior noise. Tests were conducted in a large scale fuselage model - a composite cylinder which simulates a commuter class aircraft fuselage with three sections of trim panel and a floor. Using an optimization technique based on the component transfer functions, combinations of 4 out of 8 piezoceramic actuators and 8 out of 462 microphone locations were evaluated against predicted performance. A combinatorial optimization technique call tabu search was employed to select the optimum transducer arrays. Three test frequencies represent the cases of a strong acoustic and strong structural response, a weak acoustic and strong structural response and a strong acoustic and weak structural response. Noise reduction was obtained using a Time Averaged/Gradient Descent (TAGD) controller. Results indicate that the optimization technique successfully predicted best and worst case performance. An enhancement of the TAGD control algorithm was also evaluated. The principal components of the actuator/sensor transfer functions were used in the PC-TAGD controller. The principal components are shown to be independent of each other while providing control as effective as the standard TAGD.

Palumbo, D. L.↗
DOE OSTI2021

Estimating the Adequacy of a Multi-Objective Optimization

Multi-objective optimization methods can be criticized for lacking a statistically valid measure of the quality and representativeness of a solution. This stance is especially relevant to metaheuristic optimization approaches but can also apply to other methods that typically might only report a small representative subset of a Pareto frontier. Here we present a method to address this deficiency based on random sampling of a solution space to determine, with a specified level of confidence, the fraction of the solution space that is surpassed by an optimization. The Superiority of Multi-Objective Optimization to Random Sampling, or SMORS method, can evaluate quality and representativeness using dominance or other measures, e.g., a spacing measure for high-dimensional spaces. SMORS has been tested in a combinatorial optimization context using a genetic algorithm but could be useful for other optimization methods.

42 ENGINEERING↗
DOE OSTI2024

Retrieving Top-k Hyperedge Triplets: Models and Applications

Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions can- not be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge inter- sections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

hypergraphs, motifs, Combinatorial Algorithms↗
NASA NTRS2006

Exploiting Quantum Resonance to Solve Combinatorial Problems

Quantum resonance would be exploited in a proposed quantum-computing approach to the solution of combinatorial optimization problems. In quantum computing in general, one takes advantage of the fact that an algorithm cannot be decoupled from the physical effects available to implement it. Prior approaches to quantum computing have involved exploitation of only a subset of known quantum physical effects, notably including parallelism and entanglement, but not including resonance. In the proposed approach, one would utilize the combinatorial properties of tensor-product decomposability of unitary evolution of many-particle quantum systems for physically simulating solutions to NP-complete problems (a class of problems that are intractable with respect to classical methods of computation). In this approach, reinforcement and selection of a desired solution would be executed by means of quantum resonance. Classes of NP-complete problems that are important in practice and could be solved by the proposed approach include planning, scheduling, search, and optimal design.

Zak, Michail↗
NASA NTRS2023

Automated Fiber Placement Through Thickness Defect Stacking Optimization

In its 2022 commercial market outlook, Boeing forecasted an 80% increase in the global fleet through 2041 compared to 2019 pre-pandemic levels. This sharp rise in demand will drive pressure onto airframe manufacturers to ramp up production and find more efficient ways to design and manufacture airplanes. Complicating this challenge is the industry’s recent transformation from traditional metal-based airframes towards hybrid composite-metal aircraft. While composites have been used in aviation for decades, aircraft manufacturers are still struggling to design and manufacture quality parts at a high rate. Automated Fiber Placement (AFP) is one of the main manufacturing techniques used to produce large-scale composite parts. After a design has been created, a manufacturing strategy has to be developed based on the working material, part geometry, and machine capabilities. This process planning stage is essential to the AFP workflow and currently requires a high level of manual input from an experienced process planner. In an effort to automate and optimize this stage, the Computer Aided Process Planning (CAPP) module was developed. CAPP assists process planners in identifying optimal starting point location and layup strategy for each ply of a laminate. This Ply-Level Optimization (PLO) phase operates on the quantification of ply quality through predictable geometry-based defects such as gaps, overlaps, angle deviation, and steering. As you move from PLO to Laminate-Level Optimization (LLO) the design space grows exponentially, emphasizing the need for automated optimization. The work presented in this thesis expands CAPP’s functionality by comparing the planned fiber paths through the thickness of the laminate to mitigate stacked area defects and achieve an optimal laminate-level manufacturing strategy. Within CAPP, predicted gap and overlap defects are imported from Vericut Composites Programming (VCP) and then discretized to streamline the through-thickness comparison. Two objective functions are used to score different combinations of ply layup strategies based on defect stacking both globally and locally. Four combinatorial optimization algorithms were coupled with these objective functions to investigate the laminate-level manufacturing strategy design space and converge on the optimal plan. These algorithms were evaluated based on accuracy and efficiency through virtual testing on a complex tool surface. A separate LLO approach was developed to achieve near-optimal laminates in significantly less time. The end result is a software package which greatly reduces the required input from process planners, shortening the design-build cycle time and improving part quality.

AFP↗
NASA NTRS2010

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

NASA's space data-communications infrastructure, the Space Network and the Ground Network, provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft via orbiting relay satellites and ground stations. An implementation of the methods and algorithms disclosed herein will be a system that produces globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary search, a class of probabilistic strategies for searching large solution spaces, constitutes the essential technology in this disclosure. Also disclosed are methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithm itself. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally, with applicability to a very broad class of combinatorial optimization problems.

Rash, James L.↗
NASA NTRS1993

Optimization of blade arrangement in a randomly mistuned cascade using simulated annealing

This paper presents preliminary results of an investigation on mistuning of bladed-disk assemblies aimed at capturing the benefits of mistuning on stability, while at the same time, minimizing the adverse effects on response by solving the following problem: given a set of N turbine blades, each being a small random perturbation of the same nominal blade, determine the best arrangement of the N blades in a mistuned cascade with regard to aeroelastic response. In the studies reported here, mistuning of the blades is restricted to small differences in torsional stiffness. The large combinatorial optimization problem of seeking the best arrangement by blade exchanges is solved using a simulated annealing algorithm.

Thompson, Edward A.↗
NASA NTRS2014

An Optimizing Space Data-Communications Scheduling Method and Algorithm with Interference Mitigation, Generalized for a Broad Class of Optimization Problems

NASA's space data-communications infrastructure-the Space Network and the Ground Network-provide scheduled (as well as some limited types of unscheduled) data-communications services to user spacecraft. The Space Network operates several orbiting geostationary platforms (the Tracking and Data Relay Satellite System (TDRSS)), each with its own servicedelivery antennas onboard. The Ground Network operates service-delivery antennas at ground stations located around the world. Together, these networks enable data transfer between user spacecraft and their mission control centers on Earth. Scheduling data-communications events for spacecraft that use the NASA communications infrastructure-the relay satellites and the ground stations-can be accomplished today with software having an operational heritage dating from the 1980s or earlier. An implementation of the scheduling methods and algorithms disclosed and formally specified herein will produce globally optimized schedules with not only optimized service delivery by the space data-communications infrastructure but also optimized satisfaction of all user requirements and prescribed constraints, including radio frequency interference (RFI) constraints. Evolutionary algorithms, a class of probabilistic strategies for searching large solution spaces, is the essential technology invoked and exploited in this disclosure. Also disclosed are secondary methods and algorithms for optimizing the execution efficiency of the schedule-generation algorithms themselves. The scheduling methods and algorithms as presented are adaptable to accommodate the complexity of scheduling the civilian and/or military data-communications infrastructure within the expected range of future users and space- or ground-based service-delivery assets. Finally, the problem itself, and the methods and algorithms, are generalized and specified formally. The generalized methods and algorithms are applicable to a very broad class of combinatorial-optimization problems that encompasses, among many others, the problem of generating optimal space-data communications schedules.

ground stations↗
DOE OSTI2019

Digital memcomputing: From logic to dynamics to topology

Digital memcomputing machines (DMMs) are a class of computational machines designed to solve combinatorial optimization problems. A practical realization of DMMs can be accomplished via electrical circuits of highly non-linear, point-dissipative dynamical systems engineered so that periodic orbits and chaos can be avoided. A given logic problem is first mapped into this type of dynamical system whose point attractors represent the solutions of the original problem. A DMM then finds the solution via a succession of elementary instantons whose role is to eliminate solitonic configurations of logical inconsistency (“logical defects”) from the circuit. By employing a supersymmetric theory of dynamics, a DMM can be described by a cohomological field theory that allows for computation of certain topological matrix elements on instantons that have the mathematical meaning of intersection numbers on instantons. We discuss the “dynamical” meaning of these matrix elements, and argue that the number of elementary instantons needed to reach the solution cannot exceed the number of state variables of DMMs, which in turn can only grow at most polynomially with the size of the problem. These results shed further light on the relation between logic, dynamics and topology in digital memcomputing.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Scalable and automated CRISPR-based strain engineering using droplet microfluidics

Abstract We present a droplet-based microfluidic system that enables CRISPR-based gene editing and high-throughput screening on a chip. The microfluidic device contains a 10 × 10 element array, and each element contains sets of electrodes for two electric field-actuated operations: electrowetting for merging droplets to mix reagents and electroporation for transformation. This device can perform up to 100 genetic modification reactions in parallel, providing a scalable platform for generating the large number of engineered strains required for the combinatorial optimization of genetic pathways and predictable bioengineering. We demonstrate the system’s capabilities through the CRISPR-based engineering of two test cases: (1) disruption of the function of the enzyme galactokinase ( galK ) in E. coli and (2) targeted engineering of the glutamine synthetase gene ( glnA ) and the blue-pigment synthetase gene ( bpsA ) to improve indigoidine production in E. coli .

42 ENGINEERING↗