Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “combinatorial”

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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Methods for generating barcoded combinatorial libraries

Provided herein are methods and composition for trackable genetic variant libraries. Further provided herein are methods and compositions for recursive engineering. Further provided herein are methods and compositions for multiplex engineering. Further provided herein are methods and compositions for enriching for editing and trackable engineered sequences and cells using nucleic acid-guided nucleases.

Gill, Ryan T.↗
DOE OSTI2023

Lanthanide-chelator combinatorial barcoding

Disclosed herein are methods for tracking solutions, (e.g., reaction conditions in solutions). In some embodiments, the method comprises: contacting a first lanthanide-chelator complex to a first solution to generate a first barcoded solution, wherein the first lanthanide-chelator complex comprises a first lanthanide chelated by a first chelator; contacting a second lanthanide-chelator complex to a second solution to generate a second barcoded solution, wherein the second lanthanide-chelator complex comprises a second lanthanide chelated by a second chelator; mixing the first barcoded solution and the second barcoded solution to form one or more mixtures; and identifying the first lanthanide ions in the mass spectrum and the second lanthanide ions in the mass spectrum to track the condition of each of the one or more mixtures.

Duncombe, Todd↗
DOE OSTI2023

Combinatoric Researchers at Sandia National Laboratories: An ethnographic study

Combinatorial research, the incorporation of multiple domains in a unified research agenda, is a strong contributor to the growing corpus of scientific knowledge and technological advancements worldwide. In 2019, a study team at Sandia National Laboratories (Sandia, the Labs) used a systems approach to understand if and how combinatorial research agendas were playing out at Sandia, one of America’s premiere national security research venues. The study team used the data collection effort described in this report to ground the discussion of the broad social environment and particular organizational environments within which combinatorial research agendas are developed, as described in the full study. The team interviewed twenty-five staff members engaged in combinatorial research at Sandia in New Mexico and California during the months of June – September 2019. Analysis of this corpus of ethnographic data, combined with knowledge drawn from relevant literature, concluded that there is an individual type who would be most likely to engage in combinatoric research, described by both demographic and psychographic components. This type demonstrates both intellectual depth and the curiosity which leads to breadth. The analysis also showed that Sandia as an organization and as perceived by the respondents, set up tension for the combinatorial researcher. While Sandia was generally agnostic towards combinatorial research, that agnostic posture depended on whether the researcher was able to fulfill all her customer obligations – obligations that are structured primarily in transactional relationships with customers with relatively short time horizons. This report concludes with suggestions for additional research in the ethnographic domain.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2021

Lower bounds on circuit depth of the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in noisy intermediate-scale quantum (NISQ) devices increase exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. In this work, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of vertex covering and Boolean satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A differentiable approach to the maximum independent set problem using dataless neural networks

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. Here, in this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Surfaceology for colored Yukawa theory

Arkani-Hamed and collaborators have recently shown that scattering amplitudes for colored theories can be expressed as integrals over combinatorial objects simply constructed from surfaces decorated by kinematic data. In this paper we extend the curve integral formalism to theories with colored fermionic matter and present a compact formula for the all-loop, all-genus, all-multiplicity amplitude integrand of a colored Yukawa theory. The curve integral formalism makes certain properties of the amplitudes manifest and repackages non-trivial numerators into a single combinatorial object. We also present an efficient formula for L-loop integrated amplitudes in terms of a sum over 2 L combinatorial determinants.

1/N Expansion↗
DOE OSTI2022

Printing noble metal alloy films with compositional gradient

Additive manufacturing has offered great promise in fabricating materials and devices with complex structures and unique properties. In addition to complex structures, additive manufacturing also allows for local changes to material compositions and/or structure, ideal for combinatorial material investigations. Besides, advantages over freedom of design, mass customization, waste minimization and the capability to fast prototyping, the on-demand control of compositional distributions in low dimensional materials remains challenging. In this work, we demonstrate a combinatorial aerosol jet printing technique to create noble metal films with gradient compositions. Nanoparticle sizes and ink chemistry are critical for aerosol jet printing and sintering process in order to achieve defect free thin films. Ruthenium (Ru) and platinum (Pt) nanoparticles with size <5 nm were synthesized and formulated into printable inks. Further, after thermal sintering at temperature as low as 400 °C, printed nanoparticles formed highly reflective films free from microstructural defect. Alloy films of gradient compositions were realized via in-situ mixing Ru and Pt ink streams and varying the mixing ratio during the printing process. This combinatorial printing method provides great potential to rapidly transform nanoparticle inks into new materials compositions and structures unobtainable via conventional methods for high-throughput materials studies.

36 MATERIALS SCIENCE↗
DOE OSTI2023

On relaxations of the max k -cut problem formulations

Here, a tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Thermophilic Chassis-Enabled High-Throughput Selection of a Thermostable Fluorogenic Reporter

Thermostable proteins show increased shelf life and performance at elevated temperatures and under harsh conditions, resulting in lower costs for various industrial and biotechnological applications. However, due to a limited understanding of the relationship between stability and function, protein stabilization remains primarily a trial-and-error approach. Therefore, building a combinatorial library of mutations predicted to improve stability, followed by experimental testing, represents a markedly improved methodology. However, the lack of high-throughput approaches to screen even a moderately sized library presents a major bottleneck in the field. Here, in this study, we use a thermophile, Parageobacillus thermoglucosidasius (Ptherm) to rapidly screen combinatorial libraries consisting of rationally designed thermostabilizing mutations (∼10 3 –10 4 ) of a mesophilic fluorescent reporter, Y-FAST. On a Petri dish, microbial growth at an elevated temperature and exposure to fluorogen yielded several colonies of Ptherm that showed distinct fluorescence at 55 and 68 °C in our two sequentially generated libraries using Rosetta and ProteinMPNN, respectively. The Y-FAST variants isolated from fluorescent colonies were brighter than Y-FAST and showed higher resistance to thermal and chemical denaturation. AlphaFold-predicted structures and MD simulations revealed stability-enhancing salt bridges and hydrogen bond networks in the isolated FAST variants. The moderately thermostable FAST (tsFAST) and hyperstable FAST (hsFAST) were then demonstrated as translation reporters for protein expression and folding at elevated temperatures, such as 55 and 68 °C. Our approach of combinatorial library generation and high-throughput screening in a thermophilic chassis could, in principle, be extended to other proteins fused to these translation reporters. Furthermore, the hsFAST protein is small─half the size of the green fluorescent protein─and does not require oxygen for maturation, making it ideal for engineering extremophilic anaerobes for biosensing and bioconversion.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

High-throughput screening of tribological properties of monolayer films using molecular dynamics and machine learning

Monolayer films have shown promise as a lubricating layer to reduce friction and wear of mechanical devices with separations on the nanoscale. These films have a vast design space with many tunable properties that can affect their tribological effectiveness. For example, terminal group chemistry, film composition, and backbone chemistry can all lead to films with significantly different tribological properties. This design space, however, is very difficult to explore without a combinatorial approach and an automatable, reproducible, and extensible workflow to screen for promising candidate films. Here, using the Molecular Simulation Design Framework (MoSDeF), a combinatorial screening study was performed to explore 9747 unique monolayer films (116 964 total simulations) and a machine learning (ML) model using a random forest regressor, an ensemble learning technique, to explore the role of terminal group chemistry and its effect on tribological effectiveness. The most promising films were found to contain small terminal groups such as cyano and ethylene. The ML model was subsequently applied to screen terminal group candidates identified from the ChEMBL small molecule library. Approximately 193 131 unique film candidates were screened with approximately a five order of magnitude speed-up in analysis compared to simulation alone. The ML model was thus able to be used as a predictive tool to greatly speed up the initial screening of promising candidate films for future simulation studies, suggesting that computational screening in combination with ML can greatly increase the throughput in combinatorial approaches to generate in silico data and then train ML models in a controlled, self-consistent fashion.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Neutralizing Antibodies to SARS-CoV-2 Selected from a Human Antibody Library Constructed Decades Ago

Combinatorial antibody libraries not only effectively reduce antibody discovery to a numbers game, but enable documentation of the history of antibody responses in an individual. The severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) pandemic has prompted a wider application of this technology to meet the public health challenge of pandemic threats in the modern era. Herein, a combinatorial human antibody library constructed 20 years before the coronavirus disease 2019 (COVID-19) pandemic is used to discover three highly potent antibodies that selectively bind SARS-CoV-2 spike protein and neutralize authentic SARS-CoV-2 virus. Compared to neutralizing antibodies from COVID-19 patients with generally low somatic hypermutation (SHM), these three antibodies contain over 13–22 SHMs, many of which are involved in specific interactions in their crystal structures with SARS-CoV-2 spike receptor binding domain. The identification of these somatically mutated antibodies in a pre-pandemic library raises intriguing questions about the origin and evolution of these antibodies with respect to their reactivity with SARS-CoV-2.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2023

Posiform planting: generating QUBO instances for benchmarking

We are interested in benchmarking both quantum annealing and classical algorithms for minimizing quadratic unconstrained binary optimization (QUBO) problems. Such problems are NP-hard in general, implying that the exact minima of randomly generated instances are hard to find and thus typically unknown. While brute forcing smaller instances is possible, such instances are typically not interesting due to being too easy for both quantum and classical algorithms. In this contribution, we propose a novel method, called posiform planting , for generating random QUBO instances of arbitrary size with known optimal solutions, and use those instances to benchmark the sampling quality of four D-Wave quantum annealers utilizing different interconnection structures (Chimera, Pegasus, and Zephyr hardware graphs) and the simulated annealing algorithm. Posiform planting differs from many existing methods in two key ways. It ensures the uniqueness of the planted optimal solution, thus avoiding groundstate degeneracy, and it enables the generation of QUBOs that are tailored to a given hardware connectivity structure, provided that the connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT boolean satisfiability combinatorial optimization problems. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of combinatorial optimization problems with up to 5, 627 qubits.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Tropical amplitudes for colored Lagrangians

Recently a new formulation for scattering amplitudes in Tr(Φ 3 ) theory has been given based on simple combinatorial ideas in the space of kinematic data. This allows all-loop integrated amplitudes to be expressed as “curve integrals” defined using tropical building blocks — the “headlight functions”. This paper shows how the formulation extends to the amplitudes of more general Lagrangians. We will present a number of different ways of introducing tropical “numerator functions” that allow us to describe general Lagrangian interactions. The simplest family of these “tropical numerators” computes the amplitudes of interesting Lagrangians with infinitely many interactions. We also describe methods for tropically formulating the amplitudes for general Lagrangians. One uses a variant of “Wick contraction” to glue together numerator factors for general interaction vertices. Another uses a natural characterization of polygons on surfaces to give a novel combinatorial description of all possible diagrams associated with arbitrary valence interactions.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗