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.

302 records · Page 17

All sources NASA NTRS DOE OSTI

DOE OSTI2023

HD-Bind: Encoding of Molecular Structure with Low Precision, Hyperdimensional Binary Representations

Publicly available collections of drug-like molecules have grown to comprise tens of billions of compounds due to advances in combinatorial chemistry. Traditional methods for identifying "hit" molecules from a large collection of potential drug-like candidates have relied on biophysical theory to compute approximations to the Gibbs free energy of the binding interaction between the drug and its protein target. These approaches have the major drawback that they require exceptional computing capabilities for even relatively small collections of molecules. Hyperdimensional Computing (HDC) is a recently-proposed learning paradigm that represents data with high-dimension binary vectors; this allows the use of low-precision binary vector arithmetic to create models of the data that can be learned without the need for the gradient-based optimization required in many conventional machine learning and deep learning methods. This algorithmic simplicity allows for acceleration in hardware that has been previously demonstrated in a range of application areas. We consider existing HDC approaches for molecular property classification and introduce two novel encodings of a commonly-used molecular representation, the extended connectivity fingerprint (ECFP). We show that HDC-based inference methods are as much as 91 times more efficient than traditional machine learning methods, and achieve an acceleration of nearly nine orders of magnitude compared to molecular docking. Our results show that HDC accelerated methods retain competitive accuracy on a number of well-studied tasks such as molecular property predictions using the MoleculeNet dataset, and bind/no-bind activity classification using the DUD-E and LIT-PCBA datasets. Our work thus motivates further investigation into molecular representation learning to develop ultraefficient pre-screening tools.

Jones, William↗

DOE OSTI2021

Design and Performance of a Smartphone-based Cosmic Ray Observatory

This dissertation examines the feasibility of appropriating the global network of smartphones as an observatory for ultra-high-energy cosmic rays. An application and cloud-based data-acquisition system are first proposed for such an observatory, in which heterogenous devices self-calibrate and server feedback optimizes individual device triggers. Methods of monitoring and manually controlling this network are also examined. Detection efficiencies for cosmic muons, MeV-scale gamma rays, and 120 GeV protons are then measured for this trigger, with which a Monte Carlo pixel model is fine-tuned. Extending this model to cosmic ray showers, the effective area of the observatory for super-GZK primaries is shown to equal that of the Pierre Auger Observatory with a global participation rate under 0.1%, far below initial estimates presented in Ref. [83]. A vastly improved sensitivity to photons and more precise modeling of electrons are primarily responsible for this discrepancy, though more refined models of the combinatorial background may yet lead to more stringent requirements.

Swaney, Jeff↗

DOE OSTI2023

Novel Chalcopyrites for Advanced Photoelectrochemical Water Splitting

With the support of DoE’s EERE office, our team has established a unique tool-chest of capabilities, including theoretical modeling (Lawrence Livermore National Laboratory: LLNL), state-of-the-art synthesis (Hawaii Natural Energy Institute: HNEI, Stanford, and the National Renewable Energy Laboratory: NREL) and advanced materials and interfaces characterization (University of Nevada, Las Vegas: UNLV, and Lawrence Berkeley National Laboratory: LBNL), to accelerate the development of high efficiency and durable chalcopyrite materials for advanced photoelectrochemical (PEC) water splitting. Using this synergistic approach, we have successfully created new wide bandgap chalcopyrite photocathodes generating over 10 mA/cm 2 , developed innovative strategies to protect them from corrosion, and engineered novel integration methods to circumvent thin film materials mechanical, chemical and thermal incompatibility. In Task 1 “Modeling and synthesis of chalcopyrite photocathodes”, we expanded our library of wide bandgap chalcopyrites for PEC water splitting. With support from LLNL’s “Computational Materials Diagnostics and Optimization of PEC Devices”, LBNL’s “photophysical” and NREL’s “I-III-VI Compound Semiconductors for Water-Splitting” nodes, we investigated two new chalcopyrite candidates for PEC water splitting: Cu(In,Al)Se 2 and Cu(In,B)Se 2 . We also further developed ordered vacancy compounds, such as CuGa 3 Se 5 , with unprecedented durability during PEC waters splitting in acidic solutions. In Task 2 “Interfaces engineering for enhanced efficiency and durability”, we addressed both the non-ideal band-edge positions of chalcopyrites with respect to water redox potentials, as well as their chemical instability under PEC water splitting, with a buried-junctions approach. With help from NREL’s “High-Throughput Experimental Thin Film Combinatorial Capabilities” and “Corrosion Analysis of Materials” nodes, we engineered environmentally friendly n-type buffers, including Mn x Zn 1-x O, to adjust the chalcopyrite band-edge positions and achieved photovoltages as high as 925 mV. Also, we integrated non-precious catalytic-protecting layers, such as WO 3 , to enhance the water splitting long-term stability of chalcopyrite absorbers. Finally, in Task 3 “Hybrid photoelectrode device integration”, we proposed an innovative method to bond wide bandgap photocathodes onto narrow bandgap PV drivers at room temperature using conductive polymers. Our semi-monolithic approach addressed fundamental processing incompatibility issues, as both the photocathode and the PV driver are processed separately. Proof-of-concept whole-chalcopyrite tandems were obtained by consecutive exfoliation and transfer of fully integrated 1.85 eV CuGa 3 Se 5 and 1.13 eV CuInGaSe 2 stacks from their Mo/SLG substrates onto a new single FTO host substrate.

08 HYDROGEN↗

DOE OSTI2021

Solid Phase Gradient Alloying Method via ShAPE

Alloying has been used to confer desirable properties to various metallic systems since the bronze age. For example, Ni, Mn, and Cr are alloyed into an Fe matrix to make steel, which has improved strength and corrosion resistance (as displayed in Fig. 1). In addition to the type of alloying elements, the amount of alloying elements added into a matrix is also very critical for a material’s mechanical property, physical property, machinability, and cost. Conventionally, new alloys are discovered by combining alloy precursors and elemental constituents into a mixture and melting them together. The solidified product or ingot represents a usually non-homogeneous combination of the chemistry with a microstructure dictated by the physics of solidification. It is time and energy intensive to optimize the alloying amounts via the casting process and hence, economically not conducive to rapid alloy discovery. In addition, the cast microstructure seen in the as-cast ingot is often not the ideal, nor even desired structure for optimized performance. Cast materials often need further processing such as homogenization, annealing, and deformation work put in through rolling, forging, extruding, etc. to have favorable microstructures and properties. A faster method to discover new alloy combinations and evaluate them in their worked or processed form is needed. Recently, Laser Engineered Net Shaping was applied to fabricate gradient compositional material for alloy designing. However, the mechanical properties of this gradient alloy were poor due to the existence of impurities, oxidation and cracks that are inherent in the melt-solidification process. Because of these limitations, we propose to use a solid-phase process (ShAPE) to create bulk materials (extrudates) that vary in composition from one end of the extruded solid to the other. Various manufacturing methods for alloy design including conventional casting method, laser based combinatorial method and current solid phase gradient alloying method are displayed and compared in Fig. 2. ShAPE machine and a schematic of ShAPE process are displayed in Fig. 3. Starting material is processed by a rotating and plunging die to form an extrudate. We are proposing through this methodology to invent a new, bulk-scale combinatorial technique. With this novel technique, alloying element can be dissolved into the matrix with a continued gradient without bulk melting. Formation of inter-metallics and defects originating from melt processing can be avoided. In addition, the ShAPE process creates the mixed alloy chemistry, and meanwhile subjects the material to severe plastic strain, which induces the favorable “worked” microstructure. Products from the ShAPE process can be tested in hardness directly providing a path to rapid evaluation of mechanical properties. The ability to create graded structures using friction stir processing (FSP) has been demonstrated, however using the ShAPE process we believe will lead to much faster and higher fidelity results. When combined with high throughput screening methods of physical, mechanical and microstructural property characterization, efficiency and accuracy of alloy design can be significantly improved.

36 MATERIALS SCIENCE↗

NASA NTRS1997

The Problem of Size in Robust Design

To facilitate the effective solution of multidisciplinary, multiobjective complex design problems, a departure from the traditional parametric design analysis and single objective optimization approaches is necessary in the preliminary stages of design. A necessary tradeoff becomes one of efficiency vs. accuracy as approximate models are sought to allow fast analysis and effective exploration of a preliminary design space. In this paper we apply a general robust design approach for efficient and comprehensive preliminary design to a large complex system: a high speed civil transport (HSCT) aircraft. Specifically, we investigate the HSCT wing configuration design, incorporating life cycle economic uncertainties to identify economically robust solutions. The approach is built on the foundation of statistical experimentation and modeling techniques and robust design principles, and is specialized through incorporation of the compromise Decision Support Problem for multiobjective design. For large problems however, as in the HSCT example, this robust design approach developed for efficient and comprehensive design breaks down with the problem of size - combinatorial explosion in experimentation and model building with number of variables -and both efficiency and accuracy are sacrificed. Our focus in this paper is on identifying and discussing the implications and open issues associated with the problem of size for the preliminary design of large complex systems.

Koch, Patrick N.↗

DOE OSTI2022

Universal machine learning framework for defect predictions in zinc blende semiconductors

Our article introduces a universal predictive framework for point defect formation energies and charge transition levels in a wide chemical space of zinc blende semiconductors and possible impurity atoms selected from across the periodic table. This framework was developed by leveraging high-throughput quantum mechanical simulations benchmarked using some experimental data from the literature, as well as machine learning (ML)-based regressions techniques that map unique materials descriptors to computed defect properties and yield optimized and generalizable models. Furthermore, the power and utility of these models is revealed through quick predictions for thousands of new defects and screening of low-energy impurities, which may tune the equilibrium conductivity in the semiconductor. This work presents, to our knowledge, the largest density functional theory (DFT) dataset of defect properties in semiconductors and the largest DFT+ML-based screening of point defects in semiconductors to date.

36 MATERIALS SCIENCE↗

DOE OSTI2021

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗

DOE OSTI2020

On the Solution of ℓ 0 -Constrained Sparse Inverse Covariance Estimation Problems

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ 1 regularizer to encourage sparsity is common practice, the combinatorial ℓ 0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ 0 constraint. Here, we introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ 0 -constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods.

$\ell_0$-Constrained↗

DOE OSTI2022

Quantum Distributed Unit Commitment: An Application in Microgrids

The dawn of quantum computing brings on a revolution in the way combinatorially complex power system problems such as Unit Commitment are solved. The Unit Commitment problem complexity is expected to increase in the future because of the trend toward the increase of penetration of intermittent renewables. Even though quantum computing has proven effective for solving a host of problems, its applications for power systems’ problems have been rather limited. Here, in this paper, a quantum unit commitment is innovatively formulated and the quantum version of the decomposition and coordination alternate direction method of multipliers (ADMM) is established. The above is achieved by devising quantum algorithms and by exploiting the superposition and entanglement of quantum bits (qubits) for solving subproblems, which are then coordinated through ADMM to obtain feasible solutions. The main contributions of this paper include: 1) the innovative development of a quantum model for Unit Commitment; 2) development of decomposition and coordination-supported framework which paves the way for the utilization of limited quantum resources to potentially solve the large-scale discrete optimization problems; 3) devising the novel quantum distributed unit commitment (QDUC) to solve the problem in a larger scale than currently available quantum computers are capable of solving. The QDUC results are compared with those from its classical counterpart, which validate the efficacy of quantum computing.

97 MATHEMATICS AND COMPUTING↗

NASA NTRSDate not supplied

Runway Configuration Management with Offline Reinforcement Learning

Runway configuration management (RCM) is a challenging task, and it affects the efficiency of the National Airspace System (NAS) and airport surface operations significantly. Each airport, depending on the geometry, capacity, local climate patterns, etc. has multiple configurations for the runway usage for arriving and departing flights. Many factors such as the incoming/outgoing traffic load, wind direction and speed, convective weather, cloud ceiling and other environmental factors might affect the choice of a runway configuration at any point in time. However, other factors such as safety measures and regulations, noise abatement, capacity of each configuration, and preference of the air traffic controllers (ATCs) can also play a significant role in selecting the configuration. A sub-optimal selection of the runway configuration, or delay in making configuration changes might result in significant increase in taxi times for aircraft on the surface of the airport, fuel and energy use of the aircraft, and maintenance costs. It can also lead to safety concerns, such as an aircraft performing one or more go-arounds before being able to land. All these factors make RCM an extremely important and challenging decision-making process for the ATCs. The current state of practice sets the runway configuration by the ATCs based on relevant information available at the time including weather, traffic, noise abatement, safety bounds, etc. This makes the decision-making process subjective based on the accuracy of the available information and the bias in human decision making. Unfortunately, this approach yields poor results (e.g., significant delays) if the predicted outcomes are uncertain and their relative impact is not well understood. This is especially evident when the uncertainty increases the size of possible predicted outcomes (combinatorial explosion in possible scenarios) that cannot be handled by human reasoning. On the other hand, an automated approach based on machine intelligence can make use of historical data and search through all (or significant amount of) possible scenarios under uncertainty and make well-informed decisions.

Milad Memarzadeh↗

DOE OSTI2021

Coupled Microbial-Conversion and Computational-Fluid-Dynamics (CFD) Models for Butanediol Production in Micro-Aerated Reactors

Microbial conversion of substrates to macromolecules has been widely used in the synthesis of value-added products in pharmaceutical and biotechnology industries. These bioreactions are also being investigated in the production of low-value commodities such as biofuels [1]. Gas-liquid mass-transfer and transport-reaction coupling are important challenges when designing and scaling up these reactor systems. Experiments in wellmixed small-scale reactors have enabled characterization of microbial reactivity, while their coupling with macroscale transport remains relatively unexplored. In this work, we use a coupled metabolic-CFD model to study the action of a genetically engineered microbe Zymomonas mobilis [2] on sugars to produce 2,3-Butanediol (BDO). BDO is an important hydrocarbon intermediate that can be catalytically upgraded to several fuels and chemicals [3]. An important aspect to this particular microbial conversion is the need for micro-aerated environments as opposed to traditional aerobic fermentation. Slight variations in oxygen concentration can result in competing reaction pathways that disable BDO production. Hence, gas-liquid mass transfer and transport need to be optimized in large-scale reactors to maximize BDO production, for which CFD is a valuable tool. The aerobic-fermentation CFD model previously developed by the authors [5] for simulating bubble-column and airlift reactors at scale was used in this study. The Reynolds-averaged mass, momentum and energy transport equations for interpenetrating gas and liquid phase are solved in this model along with the transport and interphase mass transfer of oxygen. Our previous work used a phenomenological model for microbial oxygen uptake that neglected microbial growth and other reaction pathways. In this work, a detailed metabolic model enabled prediction of product formation and inhibition pathways. In order to manage computational cost, we used a subcycling technique [6] that takes advantage of the clear separation in transport (~ 200 sec) and reaction (~ 2-3 hours) timescales. The CFD model is first solved to steady state, after which the metabolic model is advanced at every cell in the computational domain using the local oxygen concentration. The CFD model is then run to achieve a new steady state that provides a new oxygen distribution for the metabolic model. This process, where reaction and fluid updates are interleaved together, is iterated until reactants are completely exhausted. This work will examine the performance of different reactor designs such as bubble column and airlift reactors at scale (250-500 m3). Oxygen mass-transfer coefficient and distribution are critically analyzed among reactors, and optimization studies pertaining to aeration is presented. Furthermore, it has been observed in experiments that high BDO production may be achieved by manipulating the aerobic environment over the course of reaction, such that oxygen concentration is high during the growth phase, and very low as sugar is depleted. This characteristic will be addressed by our simulations for which a timedependent scheduling strategy for aeration is presented that maximizes BDO production. [1] Humbird, D., Davis, R., and McMillan, J., Aeration costs in stirred-tank and bubble column bioreactors, Biochemical Engineering Journal, 127, 161—166, 2017 [2] Yang, S., Mohagheghi, A., Franden, M. A., Chou, Y.-C., Chen, X., Dowe, N., Himmel, M. E., and Zhang, M., Metabolic engineering of zymomonas mobilis for 2, 3-butanediol production from lignocellulosic biomass sugars. Biotechnology for biofuels, 9(1):189, 2016 [3] Kim, S. J., Sim, H. J., Kim, J. W., Lee, Y. G., Park, Y. C., and Seo, J. H., Enhanced production of 2,3-butanediol from xylose by combinatorial engineering of xylose metabolic pathway and cofactor regeneration in pyruvate decarboxylase-deficient Saccharomyces cerevisiae. Bioresource Technology, 245:1551–1557, 2017 [4] Weller, H., Tabor, G., Jasak, H. and Fureby, C., A tensorial approach to computational continuum mechanics using object-oriented techniques, Computers in physics, 12, 6, 620--631, 1998

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

DOE OSTI2024

DyG-DPCD: A Distributed Parallel Community Detection Algorithm for Large-Scale Dynamic Graphs

Dynamic (Temporal) graphs capture the valuable evolution of real-world systems, from the continuously evolving patterns of social interactions and genetic pathways to the dynamic fluctuations of economic forces. Detecting communities for such evolving networks poses unique challenges. Detecting and analyzing the evolution of communities within dynamic graphs unlocks valuable insights into the underlying structural and temporal patterns of real-world systems. However, the sheer volume of modern graph data and the inherent complexity of the temporal dimension pose significant challenges to scalable community detection algorithms. Addressing this gap, our work explores the limited landscape of scalable distributed-memory parallel methods specifically designed for dynamic network community detection. We propose a novel parallel algorithm, DyG-DPCD (Dynamic Graph Distributed Parallel Community Detection), to detect communities in dynamic networks using the Message Passing Interface (MPI) framework. We present a vertex-centric approach, allowing us to detect communities through local optimization. Furthermore, we enhance our baseline algorithm by incorporating three heuristics, which improve the algorithm’s performance significantly while maintaining the quality of the solutions. We demonstrate the efficiency of our algorithm by experimenting on several real-world large-scale networks with hundreds of millions of edges spanning diverse domains. Notably, DyG-DPCD achieves speedups between 25× and 30× for large networks that we experimented on using NERSC compute nodes. In conclusion, our algorithm outperforms the STINGER parallel re-agglomeration algorithm by 30×.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2019

Combinatorial design of multimeric chelating peptoids for selective metal coordination

Current methods for metal chelation are generally based on multidentate organic ligands, which are generated through cumbersome multistep synthetic processes that lack flexibility for systematically varying metal-binding motifs. Octadentate ligands incorporating hydroxypyridinone or catecholamide binding moieties onto a spermine scaffold are known to display some of the highest affinities towards f-elements. Enhancing binding affinity for specific lanthanide or actinide ions however, necessitates ligand architectures that allow for modular and high throughput synthesis. Here we introduce a high-throughput combinatorial library of 16 tetrameric N -substituted glycine oligomers (peptoids) containing hydroxypyridinone or catecholamide chelating units linked via an ethylenediamine bridge and, for comparison, we also synthesized the corresponding mixed ligands derived from the spermine scaffold: 3,4,3-LI(1,2-HOPO) 2 (CAM) 2 and 3,4,3-LI(CAM) 2 (1,2-HOPO) 2 . Coordination-based luminescence studies were carried out with Eu 3+ and Tb 3+ to begin probing the properties of the new ligand architecture and revealed higher sensitization efficiency with the spermine scaffold as well as different spectroscopic features among the structural peptoid isomers. Solution thermodynamic properties of selected ligands revealed different coordination properties between the spermine and peptoid analogues with Eu 3+ stability constants log β 110 ranging from 28.88 ± 3.45 to 43.97 ± 0.49. The general synthetic strategy presented here paves the way for precision design of new specific and versatile ligands, with a variety of applications tailored towards the use of f-elements, including separations, optical device optimization, and pharmaceutical development.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2020

A combined machine learning and density functional theory study of binary Ti-Nb and Ti-Zr alloys: Stability and Young’s modulus

The multicomponent Ti alloys, specifically the -phase, have experienced a strong growth over the last decades, due to their outstanding properties of ultra-high strength and low Young’s modulus. These properties play a significant role in many aerospace and biomedical applications. Selection and optimization of multicomponent alloys is challenging due to the vast chemical and compositional space. Here we investigate the use of machine learning techniques informed by density functional calculations to guide the selection of Nb- and Zr-based Ti binary alloys. From the cubic structures obtained from high throughput calculations and literature, we identify several structures with Young’s moduli below 40 GPa. The multivariant decision tree methods provide efficient surrogate models to identify structure variables have high influences on the energetic stability and Young’s modulus. Furthermore, we implement a workflow of incorporating DFT provided results and machine learning method to explore the chemical and composition space of other binary and multicomponent alloys, to eventually accelerate the material design via taking advantages of identified key variables.

36 MATERIALS SCIENCE↗