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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 91 records · Page 5

All sources NASA NTRS DOE OSTI

DOE OSTI2025

Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NASA NTRS1992

Minimizing distortion in truss structures - A Hopfield network solution

Distortions in truss structures can result from random errors in element lengths that are typical of a manufacturing process. These distortions may be minimized by an optimal selection of elements from those available for placement between the prescribed nodes - a combinatorial optimization problem requiring significant investment of computational resource for all but the smallest problems. The present paper describes a formulation in which near-optimal element assignments are obtained as minimum-energy stable states, of an analogous Hopfield neural network. This requires mapping of the optimization problem into an energy function of the appropriate Liapunov form. The computational architecture is ideally suited to a parallel processor implementation and offers significant savings in computational effort. A numerical implementation of the approach is discussed with reference to planar truss problems.

Fu, B.↗

NASA NTRS1993

Minimizing distortion in truss structures -- a Hopfield network solution

Distortions in truss structures can result from random errors in elemental lengths that are typical of a manufacturing process. These distortions may be minimized by an optimal selection of elements from those available for placement between the prescribed nodes -- a combinatorial optimization problem requiring significant investment of computational resource for all but the smallest problems. The present paper describes a formulation in which near-optimal element assignments are obtained as minimum energy, stable states, of an analogous Hopfield neural network. This requires mapping of the optimization problem into an energy function of the appropriate Lyapunov form. The computational architecture is ideally suited to a parallel processor implementation and offers significant savings in computational effort. A numerical implementation of the approach is discussed with reference to planar truss problems.

Fu, B.↗

DOE OSTI2016

Penalty-free method for multi-constrained optimization problems based on parallel simulated annealing

A method is presented for addressing constraints within the context of large-scale combinatorial optimization problems. The method, based on constraint annealing, eliminates the use of traditional constraint penalty factors by treating each constraint as separate and concurrently solved minimization problems within a global optimization search framework. Results are demonstrated for a core loading pattern optimization problem. (authors)

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1989

Selection of active member locations in adaptive structures

The effective use of multiple passive and active members in adaptive structures necessitates that these members be optimally distributed throughout the structure. In truss structures, the problem falls into the class of combinatorial optimization for which the solution becomes exceedingly intractable as the problem size increases. This is overcome by using the simulated annealing algorithm to obtain near optimal locations for passive and/or active members. The maximization of the rate of energy dissipation over a finite time period as the measure of optimality is adopted. The selection of optimal locations for both passive and active members is consistently treated through the use of the energy dissipation rate criterion within the simulated annealing algorithm. Numerical examples are used to illustrate the effectiveness of the methodology for large truss structures.

Chen, G.-S.↗

NASA NTRS1993

Optimal placement of tuning masses on truss structures by genetic algorithms

Optimal placement of tuning masses, actuators and other peripherals on large space structures is a combinatorial optimization problem. This paper surveys several techniques for solving this problem. The genetic algorithm approach to the solution of the placement problem is described in detail. An example of minimizing the difference between the two lowest frequencies of a laboratory truss by adding tuning masses is used for demonstrating some of the advantages of genetic algorithms. The relative efficiencies of different codings are compared using the results of a large number of optimization runs.

Ponslet, Eric↗

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 NTRS1987

Optimal placement of excitations and sensors for verification of large dynamical systems

The computationally difficult problem of the optimal placement of excitations and sensors to maximize the observed measurements is studied within the framework of combinatorial optimization, and is solved numerically using a variation of the simulated annealing heuristic algorithm. Results of numerical experiments including a square plate and a 960 degrees-of-freedom Control of Flexible Structure (COFS) truss structure, are presented. Though the algorithm produces suboptimal solutions, its generality and simplicity allow the treatment of complex dynamical systems which would otherwise be difficult to handle.

Salama, M.↗

NASA NTRS2017

Quantum Approximate Optimization with Hard and Soft Constraints

Challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms. Small universal quantum computers will emerge in the next year or two, enabling a substantial broadening of the types of quantum heuristics that can be investigated beyond quantum annealing. The immediate question is What experiments should we prioritize that will give us insight into quantum heuristics? One leading candidate is the quantum approximate optimization algorithm (QAOA) metaheuristic. Here, we provide a framework for designing QAOA circuits for a variety of combinatorial optimization problems with both hard constraints that must be met and soft constraints whose violation we wish to minimize. We work through a number of examples, and discuss design principles and implementation considerations.

Hadfield, Stuart↗

DOE OSTI2016

Dynamic model-based sensor network design algorithm for system efficiency maximization

Here, a dynamic model-based sensor network design (DMSND) algorithm has been developed for maximizing system efficiency for an estimator-based control system. The algorithm synthesizes the optimal sensor network in the face of disturbances or set point changes. Computational expense of the large-scale combinatorial optimization problem is significantly reduced by parallel computing and by using combination of three novel strategies: multi-rate sampling frequency, model order reduction, and use of an incumbent solution that enables early termination of evaluation of infeasible sensor sets. The developed algorithm is applied to an acid gas removal unit as part of an integrated gasification combined cycle power plant with carbon capture. Even though there are more than thousand process states and more than hundred candidate sensor locations, the optimal sensor network design problem for maximizing process efficiency could be solved within couple of hours for a given budget.

47 OTHER INSTRUMENTATION↗

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 OSTI2017

Nonlinear Dynamic Model-Based Multiobjective Sensor Network Design Algorithm for a Plant with an Estimator-Based Control System

Here, a novel sensor network design (SND) algorithm is developed for maximizing process efficiency while minimizing sensor network cost for a nonlinear dynamic process with an estimator-based control system. The multiobjective optimization problem is solved following a lexicographic approach where the process efficiency is maximized first followed by minimization of the sensor network cost. The partial net present value, which combines the capital cost due to the sensor network and the operating cost due to deviation from the optimal efficiency, is proposed as an alternative objective. The unscented Kalman filter is considered as the nonlinear estimator. The large-scale combinatorial optimization problem is solved using a genetic algorithm. The developed SND algorithm is applied to an acid gas removal (AGR) unit as part of an integrated gasification combined cycle (IGCC) power plant with CO 2 capture. Due to the computational expense, a reduced order nonlinear model of the AGR process is identified and parallel computation is performed during implementation.

Lexicographic optimization↗

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.↗