SEARCH · Engineering Papers

Results for “combinatorial optimization problem”

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

NASA NTRS1991

Optimal actuator placement on an active reflector using a modified simulated annealing technique

The development of a lightweight actuation system for maintaining the surface accuracy of a composite honeycomb panel using piezoelectric actuators is discussed. A modified simulated annealing technique is used to optimize the problem with both combinatorial and continuous criteria and with inequality constraints. Near optimal solutions for the location of the actuators, using combinatorial optimization, and for the required actuator forces, employing continuous optimization, are sought by means of the modified simulated annealing technique. The actuator locations are determined by first seeking a near optimum solution using the modified simulated annealing technique. The final actuator configuration consists of an arrangement wherein the piezoelectric actuators are placed along six radial lines. Numerical results showing the achievable surface correction by means of this configuration are presented.

Kuo, Chin-Po↗

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

DOE OSTI2023

Material Identification From Radiographs Without Energy Resolution

We propose a method for performing material identification from radiographs without energy-resolved measurements. Material identification has a wide variety of applications, including in biomedical imaging, nondestructive testing, and security. While existing techniques for radiographic material identification make use of dual energy sources, energy-resolving detectors, or additional (e.g., neutron) measurements, such setups are not always practical— requiring additional hardware and complicating imaging. We tackle material identification without energy resolution, allowing standard X-ray systems to provide material identification information without requiring additional hardware. Assuming a setting where the geometry of each object in the scene is known and the materials come from a known set of possible materials, we pose the problem as a combinatorial optimization with a loss function that accounts for the presence of scatter and an unknown gain and propose a branch and bound algorithm to efficiently solve it. We present experiments on both synthetic data and real, experimental data with relevance to security applications— thick, dense objects imaged with MeV X-rays. We show that material identification can be efficient and accurate, for example, in a scene with three shells (two copper, one aluminum), our algorithm ran in six minutes on a consumer-level laptop and identified the correct materials as being among the top 10 best matches out of 8,000 possibilities.

36 MATERIALS SCIENCE↗

DOE OSTI2021

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N " M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N$\gg$M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1990

Programmable synaptic devices for electronic neural nets

The architecture, design, and operational characteristics of custom VLSI and thin film synaptic devices are described. The devices include CMOS-based synaptic chips containing 1024 reprogrammable synapses with a 6-bit dynamic range, and nonvolatile, write-once, binary synaptic arrays based on memory switching in hydrogenated amorphous silicon films. Their suitability for embodiment of fully parallel and analog neural hardware is discussed. Specifically, a neural network solution to an assignment problem of combinatorial global optimization, implemented in fully parallel hardware using the synaptic chips, is described. The network's ability to provide optimal and near optimal solutions over a time scale of few neuron time constants has been demonstrated and suggests a speedup improvement of several orders of magnitude over conventional search methods.

Moopenn, A.↗

NASA NTRS1991

AI techniques for a space application scheduling problem

Scheduling is a very complex optimization problem which can be categorized as an NP-complete problem. NP-complete problems are quite diverse, as are the algorithms used in searching for an optimal solution. In most cases, the best solutions that can be derived for these combinatorial explosive problems are near-optimal solutions. Due to the complexity of the scheduling problem, artificial intelligence (AI) can aid in solving these types of problems. Some of the factors are examined which make space application scheduling problems difficult and presents a fairly new AI-based technique called tabu search as applied to a real scheduling application. the specific problem is concerned with scheduling application. The specific problem is concerned with scheduling solar and stellar observations for the SOLar-STellar Irradiance Comparison Experiment (SOLSTICE) instrument in a constrained environment which produces minimum impact on the other instruments and maximizes target observation times. The SOLSTICE instrument will gly on-board the Upper Atmosphere Research Satellite (UARS) in 1991, and a similar instrument will fly on the earth observing system (Eos).

Thalman, N.↗

DOE OSTI2022

Parallel simulated annealing with embedded machine learning and multifidelity models for reactor core design

This paper presents extensions to a penalty-free, parallel simulated annealing (SA) algorithm for multi-constrained combinatorial optimization with the aim of embedding multi-fidelity physics models into the annealing procedure. The method uses a low-fidelity, quickly executing model for rapid design space exploration and a high-fidelity model for detailed constraint resolution and on-the-fly bias correction. Machine learning models updated within the annealing procedure were used to bridge the gap between the multi-fidelity models, which led to accurate rapid exploration and efficient detailed constraint resolution. A software implementation of the new multi-fidelity optimization methods, called ML-PSA, was demonstrated on a continuous multi-fidelity optimization problem and a constrained combinatorial PWR lattice design problem. These problems demonstrate some of the features, parallel performance characteristics, and extensible nature of the multi-fidelity SA methods. This paper shows that the developed software and procedure are a general optimization tool that can be applied to a wide variety of scientific and engineering design optimization applications. (authors)

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

DOE OSTI2026

Robust Optimal Experimental Design of Infinite-Dimensional Bayesian Nonlinear Inverse Problems

Abstract. We consider robust optimal experimental design (ROED) for nonlinear Bayesian inverse problems governed by partial differential equations (PDEs). An optimal design is one that maximizes some utility quantifying the quality of the solution of an inverse problem. However, the optimal design is dependent on elements of the inverse problem such as the simulation model, the prior, or the measurement error model. ROED aims to produce an optimal design that is aware of the additional uncertainties encoded in the inverse problem and remains optimal even after variations in them. We follow a worst-case scenario approach to develop a new framework for robust optimal design of nonlinear Bayesian inverse problems. The proposed framework (a) is scalable and designed for infinite-dimensional Bayesian nonlinear inverse problems constrained by PDEs; (b) develops efficient approximations of the utility, namely the expected information gain; (c) employs eigenvalue sensitivity techniques to develop analytical forms and efficient evaluation methods of the gradient of the utility with respect to the uncertainties against which we wish to be robust; and (d) employs a probabilistic optimization paradigm that properly defines and efficiently solves the resulting combinatorial max-min optimization problem. The effectiveness of the proposed approach is illustrated for optimal sensor placement problem in an inverse problem governed by an elliptic PDE.

Chowdhary, Abhijit↗

NASA NTRS2002

Combinatorial Multiobjective Optimization Using Genetic Algorithms

The research proposed in this document investigated multiobjective optimization approaches based upon the Genetic Algorithm (GA). Several versions of the GA have been adopted for multiobjective design, but, prior to this research, there had not been significant comparisons of the most popular strategies. The research effort first generalized the two-branch tournament genetic algorithm in to an N-branch genetic algorithm, then the N-branch GA was compared with a version of the popular Multi-Objective Genetic Algorithm (MOGA). Because the genetic algorithm is well suited to combinatorial (mixed discrete / continuous) optimization problems, the GA can be used in the conceptual phase of design to combine selection (discrete variable) and sizing (continuous variable) tasks. Using a multiobjective formulation for the design of a 50-passenger aircraft to meet the competing objectives of minimizing takeoff gross weight and minimizing trip time, the GA generated a range of tradeoff designs that illustrate which aircraft features change from a low-weight, slow trip-time aircraft design to a heavy-weight, short trip-time aircraft design. Given the objective formulation and analysis methods used, the results of this study identify where turboprop-powered aircraft and turbofan-powered aircraft become more desirable for the 50 seat passenger application. This aircraft design application also begins to suggest how a combinatorial multiobjective optimization technique could be used to assist in the design of morphing aircraft.

Crossley, William A.↗

DOE OSTI2025

Quantum Adiabatic Optimization with Rydberg Arrays: Localization Phenomena and Encoding Strategies

Quantum adiabatic optimization seeks to solve combinatorial problems using quantum dynamics, requiring the Hamiltonian of the system to align with the problem of interest. However, these Hamiltonians are often incompatible with the native constraints of quantum hardware, necessitating encoding strategies to map the original problem into a hardware-conformant form. While the classical overhead associated with such mappings is easily quantifiable and typically polynomial in problem size, it is much harder to quantify their overhead on the quantum algorithm, e.g., the transformation of the adiabatic timescale. In this work, we address this challenge on the concrete example of the encoding scheme proposed in [Nguyen , PRX Quantum , 010316 (2023)], which is designed to map optimization problems on arbitrarily connected graphs into Rydberg atom arrays. We consider the fundamental building blocks underlying this encoding scheme and determine the scaling of the minimum gap with system size along adiabatic protocols. Even when the original problem is trivially solvable, we find that the encoded problem can exhibit an exponentially closing minimum gap. We show that this originates from a quantum coherent effect, which gives rise to an unfavorable localization of the ground-state wave function. On the QuEra Aquila neutral atom machine, we observe such localization and its effect on the success probability of finding the correct solution to the encoded optimization problem. Finally, we propose quantum-aware modifications of the encoding scheme that avoid this quantum bottleneck and lead to an exponential improvement in the adiabatic performance. This highlights the crucial importance of accounting for quantum effects when designing strategies to encode classical problems onto quantum platforms. Published by the American Physical Society 2025

Bombieri, Lisa (ORCID:0009000950422897)↗

DOE OSTI2023

Graph Sparsification by Approximate matrix Multiplication

Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of sparsifying a weighted graph, while sharing the same vertices as the original graph but reducing the number of edges, is through spectral sparsification. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians, without requiring spectral information. Through the CR–MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Here, we define a new notion of additive spectral sparsifiers, which has not been considered in the literature.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Multi-objective optimization of PWR core design using NSGA-II in RAVEN’s optimization framework

Designing an PWR loading pattern is a combinatorial problem challenging to solve by brute force or traditional methods due to the sheer amount of possible combination, and constraints. Nature-inspired algorithms, such as the genetic algorithm, have demonstrated the potential to tackle this problem. The goal of this work was to improve and demonstrate the capabilities for constrained, multi-objective optimization (MOO) of loading patterns using NSGA-II in RAVEN’s optimization framework.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

DOE OSTI2021

Relaxed Multibang Regularization for the Combinatorial Integral Approximation

Multibang regularization and combinatorial integral approximation decompositions are two actively researched techniques for integer optimal control. In this work, we consider a class of polyhedral functions that arise particularly as convex lower envelopes of multibang regularizers and show that they have beneficial properties with respect to regularization of relaxations of integer optimal control problems. We extend the algorithmic framework of the combinatorial integral approximation such that a subsequence of the computed discrete-valued controls converges to the infimum of the regularized integer control problem.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1997

Quantum Resonance Approach to Combinatorial Optimization

It is shown that quantum resonance can be used for combinatorial optimization. The advantage of the approach is in independence of the computing time upon the dimensionality of the problem. As an example, the solution to a constraint satisfaction problem of exponential complexity is demonstrated.

combinatorial optimization quantum resonance↗

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

NASA NTRS2009

Physical Principle for Generation of Randomness

A physical principle (more precisely, a principle that incorporates mathematical models used in physics) has been conceived as the basis of a method of generating randomness in Monte Carlo simulations. The principle eliminates the need for conventional random-number generators. The Monte Carlo simulation method is among the most powerful computational methods for solving high-dimensional problems in physics, chemistry, economics, and information processing. The Monte Carlo simulation method is especially effective for solving problems in which computational complexity increases exponentially with dimensionality. The main advantage of the Monte Carlo simulation method over other methods is that the demand on computational resources becomes independent of dimensionality. As augmented by the present principle, the Monte Carlo simulation method becomes an even more powerful computational method that is especially useful for solving problems associated with dynamics of fluids, planning, scheduling, and combinatorial optimization. The present principle is based on coupling of dynamical equations with the corresponding Liouville equation. The randomness is generated by non-Lipschitz instability of dynamics triggered and controlled by feedback from the Liouville equation. (In non-Lipschitz dynamics, the derivatives of solutions of the dynamical equations are not required to be bounded.)

Zak, Michail↗

DOE OSTI2024

SPARTAN (Scalable Probabilistic Application Reconfigurable Tensor Autonomous Network)

The technical founder of Ludwig Computing Inc has been competitively selected for support by Cyclotron Road, a U.S. Department of Energy (DOE) Advanced Manufacturing Office (AMO) Lab-Embedded Entrepreneurship Program (LEEP) through an approved merit review process. Ludwig Computing Inc, supported by the U.S. Department of Energy's Advanced Manufacturing Office through the Cyclotron Road program, has investigated the advantages of probabilistic computing for real-world compute-intensive applications. This research adds to the understanding of alternative computing paradigms by exploring a unique hardware-software co-design that integrates quantum computing methods with nature-inspired problem-solving techniques. The project's focus on areas such as combinatorial optimization, graph analytics, and machine learning demonstrates the potential for significant advancements in computational efficiency and performance. By harnessing natural randomness to streamline large circuits into fewer devices, Ludwig's approach enables massive parallelism, potentially offering higher throughput, speed, and energy efficiency compared to conventional hardware solutions. This work benefits the public by paving the way for more efficient computing solutions that could address complex real-world problems while potentially reducing energy consumption in data-intensive industries.

97 MATHEMATICS AND COMPUTING↗