Search NASA⌕ Search

SEARCH · Search NASA

Results for “combinatorial algorithms”

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 289 records · Page 16

PTM‐Psi : A python package to facilitate the computational investigation of p ost‐ t ranslational m odification on p rotein s tructures and their i mpacts on dynamics and functions

Abstract Post‐translational modification (PTM) of a protein occurs after it has been synthesized from its genetic template, and involves chemical modifications of the protein's specific amino acid residues. Despite of the central role played by PTM in regulating molecular interactions, particularly those driven by reversible redox reactions, it remains challenging to interpret PTMs in terms of protein dynamics and function because there are numerous combinatorially enormous means for modifying amino acids in response to changes in the protein environment. In this study, we provide a workflow that allows users to interpret how perturbations caused by PTMs affect a protein's properties, dynamics, and interactions with its binding partners based on inferred or experimentally determined protein structure. This Python‐based workflow, called PTM‐Psi , integrates several established open‐source software packages, thereby enabling the user to infer protein structure from sequence, develop force fields for non‐standard amino acids using quantum mechanics, calculate free energy perturbations through molecular dynamics simulations, and score the bound complexes via docking algorithms. Using the S ‐nitrosylation of several cysteines on the GAP2 protein as an example, we demonstrated the utility of PTM‐Psi for interpreting sequence–structure–function relationships derived from thiol redox proteomics data. We demonstrate that the S ‐nitrosylated cysteine that is exposed to the solvent indirectly affects the catalytic reaction of another buried cysteine over a distance in GAP2 protein through the movement of the two ligands. Our workflow tracks the PTMs on residues that are responsive to changes in the redox environment and lays the foundation for the automation of molecular and systems biology modeling.

59 BASIC BIOLOGICAL SCIENCES↗

A Novel Application of Parallel Betweenness Centrality to Power Grid Contingency Analysis

In Energy Management Systems, contingency analysis is commonly performed for identifying and mitigating potentially harmful power grid component failures. The exponentially increasing combinatorial number of failure modes imposes a significant computational burden for massive contingency analysis. It is critical to select a limited set of high-impact contingency cases within the constraint of computing power and time requirements to make it possible for real-time power system vulnerability assessment. In this paper, we present a novel application of parallel betweenness centrality to power grid contingency selection. We cross-validate the proposed method using the model and data of the western US power grid, and implement it on a Cray XMT system - a massively multithreaded architecture - leveraging its advantages for parallel execution of irregular algorithms, such as graph analysis. We achieve a speedup of 55 times (on 64 processors) compared against the single-processor version of the same code running on the Cray XMT. We also compare an OpenMP-based version of the same code running on an HP Superdome shared-memory machine. The performance of the Cray XMT code shows better scalability and resource utilization, and shorter execution time for large-scale power grids. This proposed approach has been evaluated in PNNL’s Electricity Infrastructure Operations Center (EIOC). It is expected to provide a quick and efficient solution to massive contingency selection problems to help power grid operators to identify and mitigate potential widespread cascading power grid failures in real time.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Epistatic Net allows the sparse spectral regularization of deep neural networks for inferring fitness functions

Abstract Despite recent advances in high-throughput combinatorial mutagenesis assays, the number of labeled sequences available to predict molecular functions has remained small for the vastness of the sequence space combined with the ruggedness of many fitness functions. While deep neural networks (DNNs) can capture high-order epistatic interactions among the mutational sites, they tend to overfit to the small number of labeled sequences available for training. Here, we developed Epistatic Net (EN), a method for spectral regularization of DNNs that exploits evidence that epistatic interactions in many fitness functions are sparse. We built a scalable extension of EN, usable for larger sequences, which enables spectral regularization using fast sparse recovery algorithms informed by coding theory. Results on several biological landscapes show that EN consistently improves the prediction accuracy of DNNs and enables them to outperform competing models which assume other priors. EN estimates the higher-order epistatic interactions of DNNs trained on massive sequence spaces-a computational problem that otherwise takes years to solve.

Aghazadeh, Amirali (ORCID:0000000302230873)↗

WE-AB-BRA-12: Post-Implant Dosimetry in Prostate Brachytherapy by X-Ray and MRI Fusion

Purpose: For post-implant dosimetric assessment after prostate brachytherapy, CT-MR fusion approach has been advocated due to the superior accuracy on both seeds localization and soft tissue delineation. However, CT deposits additional radiation to the patient, and seed identification in CT requires manual review and correction. In this study, we propose an accurate, low-dose, and cost-effective post-implant dosimetry approach based on X-ray and MRI. Methods: Implanted seeds are reconstructed using only three X-ray fluoroscopy images by solving a combinatorial optimization problem. The reconstructed seeds are then registered to MR images using an intensity-based points-to-volume registration. MR images are first pre-processed by geometric and Gaussian filtering, yielding smooth candidate seed-only images. To accommodate potential soft tissue deformation, our registration is performed in two steps, an initial affine followed by local deformable registrations. An evolutionary optimizer in conjunction with a points-to-volume similarity metric is used for the affine registration. Local prostate deformation and seed migration are then adjusted by the deformable registration step with external and internal force constraints. Results: We tested our algorithm on twenty patient data sets. For quantitative evaluation, we obtained ground truth seed positions by fusing the post-implant CT-MR images. Seeds were semi-automatically extracted from CT and manually corrected and then registered to the MR images. Target registration error (TRE) was computed by measuring the Euclidean distances from the ground truth to the closest registered X-ray seeds. The overall TREs (mean±standard deviation in mm) are 1.6±1.1 (affine) and 1.3±0.8 (affine+deformable). The overall computation takes less than 1 minute. Conclusion: It has been reported that the CT-based seed localization error is ∼1.6mm and the seed localization uncertainty of 2mm results in less than 5% deviation of prostate D90. The average error of 1.3mm with our system outperforms the CT-based approach and is considered well within the clinically acceptable limit. Supported in part by NIH/NCI grant 5R01CA151395. The X-ray-based implant reconstruction method (US patent No. 8,233,686) was licensed to Acoustic MedSystems Inc.

60 APPLIED LIFE SCIENCES↗

Combinatorial Evaluation of Physical Feature Engineering, Classical Machine Learning, and Deep Learning Models for Synchrophasor Data at Scale

A major objective of the project was to train and evaluate the effectiveness of multiple event and anomaly detection, identification and classification deep temporal learning models for processing of real-time phasor measurement unit (PMU) data streams. A vast dataset, consisting of two years of phasor measurements from all three U.S. Interconnections, was curated and released by the Department of Energy (DOE) through Pacific Northwest National Laboratory (PNNL). The dataset also included an event log that provided event times and types (e.g. generator trips, line trips, planned service events, transformer operations, etc.). Our analysis of this dataset addressed six (6) of the eleven (11) research priorities identified in Funding Opportunity Announcement (FOA) DE-FOA-0001861 “Big Data Analysis of Synchrophasor Data” (FOA 1861). Rather than being limited to pre-determined specific algorithms, this project relied on the uniquely structured, highly performant underlying time series database capabilities of the PredictiveGrid platform to assess the vast dataset utilizing a wide variety of algorithms.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Are better combinations of DERs more profitable?: Combinatorial optimization for aggregation of DERs in wholesale electricity markets

Recently, regulatory changes in various countries have enabled the participation of small-scale distributed energy resources (DERs) aggregated in virtual power plants (VPPs) in wholesale electricity markets. The inherent uncertainty and variability of resources comprising VPPs can lead to imbalances between forecasted and metered outputs, potentially resulting in the deficient settlement of generation under imbalance settlement rules. To address this challenge, it is essential to manage variability in the planning phase and uncertainty in the operation phase. Most current research focuses on managing forecasting errors in the operational phase, with insufficient attention given to the planning phase. Here, to bridge this gap, this paper proposes an optimal combination strategy for DERs to maximize the market participation revenue of VPPs by proactively managing variability in the planning phase. To estimate the expected revenue, we conducted analyses for homogeneous and heterogeneous DERs using Monte Carlo simulations and genetic algorithms. Remarkably, the proposed method demonstrated approximately 8 % higher revenue compared to the neighboring group case when considering diversity in DER set configuration with equal proportions of photovoltaics and wind.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Magnetism in metastable and annealed compositionally complex alloys

Compositionally complex materials (CCMs) present a potential paradigm shift in the design of magnetic materials. These alloys exhibit long-range structural order coupled with limited or no chemical order. As a result, extreme local environments exist with a large variations in the magnetic energy terms, which can manifest large changes in the magnetic behavior. In the current work, the magnetic properties of (Cr, Mn, Fe, Ni) alloys are presented. These materials were prepared by room-temperature combinatorial sputtering, resulting in a range of compositions with a single bcc structural phase and no chemical ordering. The combinatorial growth technique allows CCMs to be prepared outside of their thermodynamically stable phase, enabling the exploration of otherwise inaccessible order. The mixed ferromagnetic and antiferromagnetic interactions in these alloys causes frustrated magnetic behavior, which results in an extremely low coercivity (<1mT), which increases rapidly at 50 K. At low temperatures, the coercivity achieves values of nearly 500 mT, which is comparable to some high-anisotropy magnetic materials. Further, commensurate with the divergent coercivity is an atypical drop in the temperature dependent magnetization. These effects are explained by a mixed magnetic phase model, consisting of ferro-, antiferro-, and frustrated magnetic regions, and are rationalized by simulations. A machine-learning algorithm is employed to visualize the parameter space and inform the development of subsequent compositions. Annealing the samples at 600 °C orders the sample, more-than doubling the Curie temperature and increasing the saturation magnetization by as much as 5×. Simultaneously, the large coercivities are suppressed, resulting in magnetic behavior that is largely temperature independent over a range of 350 K. The ability to transform from a hard magnet to a soft magnet over a narrow temperature range makes these materials promising for heat-assisted recording technologies.

36 MATERIALS SCIENCE↗

On Modeling and Analysis of MIMO Wireless Mesh Networks with Triangular Overlay Topology

Multiple input multiple output (MIMO) wireless mesh networks (WMNs) aim to provide the last-mile broadband wireless access to the Internet. Along with the algorithmic development for WMNs, some fundamental mathematical problems also emerge in various aspects such as routing, scheduling, and channel assignment, all of which require an effective mathematical model and rigorous analysis of network properties. In this paper, we propose to employ Cartesian product of graphs (CPG) as a multichannel modeling approach and explore a set of unique properties of triangular WMNs. In each layer of CPG with a single channel, we design a node coordinate scheme that retains the symmetric property of triangular meshes and develop a function for the assignment of node identity numbers based on their coordinates. We also derive a necessary-sufficient condition for interference-free links and combinatorial formulas to determine the number of the shortest paths for channel realization in triangular WMNs.

97 MATHEMATICS AND COMPUTING↗

Novel Geometric Operations for Linear Programming

This report summarizes the work performed under the project "Linear Programming in Strongly Polynomial Time." Linear programming (LP) is a classic combinatorial optimization problem heavily used directly and as an enabling subroutine in integer programming (IP). Specifically IP is the same as LP except that some solution variables must take integer values (e.g. to represent yes/no decisions). Together LP and IP have many applications in resource allocation including general logistics, and infrastructure design and vulnerability analysis. The project was motivated by the PI's recent success developing methods to efficiently sample Voronoi vertices (essentially finding nearest neighbors in high-dimensional point sets) in arbitrary dimension. His method seems applicable to exploring the high-dimensional convex feasible space of an LP problem. Although the project did not provably find a strongly-polynomial algorithm, it explored multiple algorithm classes. The new medial simplex algorithms may still lead to solvers with improved provable complexity. We describe medial simplex algorithms and some relevant structural/complexity results. We also designed a novel parallel LP algorithm based on our geometric insights and implemented it in the Spoke-LP code. A major part of the computational step is many independent vector dot products. Our parallel algorithm distributes the problem constraints across processors. Current commercial and high-quality free LP solvers require all problem details to fit onto a single processor or multicore. Our new algorithm might enable the solution of problems too large for any current LP solvers. We describe our new algorithm, give preliminary proof-of-concept experiments, and describe a new generator for arbitrarily large LP instances.

97 MATHEMATICS AND COMPUTING↗

Optimization Method to Branch and Bound Large SBO State Spaces Under Dynamic Probabilistic Risk Assessment via use of LENDIT Scales and S2R2 Sets

Traditional Probabilistic Risk Assessment (PRA) methods have been developed and are quite effective in evaluating risk associated with complex systems, but lack the capability to evaluate complex dynamic systems. These time and energy scales associated with the transient may vary as a function of transition time to a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems, while complete, results in issues associated with combinatorial explosion. In order to address the combinatorial complexity arising from the number of possible state configurations and discretization of transition times, a characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets – ‘state, system, resource and response’ (S2R2) – describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to ‘branch and bound’ the state space investigated by DPRA. In this paper we introduce the concept of LENDIT scales and S2R2 sets applied to a branch-and-bound algorithm and apply the methods to a station black out transient (SBO).

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Advantages of Unfair Quantum Ground-State Sampling

The debate around the potential superiority of quantum annealers over their classical counterparts has been ongoing since the inception of the field. Recent technological breakthroughs, which have led to the manufacture of experimental prototypes of quantum annealing optimizers with sizes approaching the practical regime, have reignited this discussion. However, the demonstration of quantum annealing speedups remains to this day an elusive albeit coveted goal. We examine the power of quantum annealers to provide a different type of quantum enhancement of practical relevance, namely, their ability to serve as useful samplers from the ground-state manifolds of combinatorial optimization problems. We study, both numerically by simulating stoquastic and non-stoquastic quantum annealing processes, and experimentally, using a prototypical quantum annealing processor, the ability of quantum annealers to sample the ground-states of spin glasses differently than thermal samplers. We demonstrate that (i) quantum annealers sample the ground-state manifolds of spin glasses very differently than thermal optimizers (ii) the nature of the quantum fluctuations driving the annealing process has a decisive effect on the final distribution, and (iii) the experimental quantum annealer samples ground-state manifolds significantly differently than thermal and ideal quantum annealers. We illustrate how quantum annealers may serve as powerful tools when complementing standard sampling algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Two Methods for Efficient Solution of the Hitting-Set Problem

A paper addresses much of the same subject matter as that of Fast Algorithms for Model-Based Diagnosis (NPO-30582), which appears elsewhere in this issue of NASA Tech Briefs. However, in the paper, the emphasis is more on the hitting-set problem (also known as the transversal problem), which is well known among experts in combinatorics. The authors primary interest in the hitting-set problem lies in its connection to the diagnosis problem: it is a theorem of model-based diagnosis that in the set-theory representation of the components of a system, the minimal diagnoses of a system are the minimal hitting sets of the system. In the paper, the hitting-set problem (and, hence, the diagnosis problem) is translated from a combinatorial to a computational problem by mapping it onto the Boolean satisfiability and integer- programming problems. The paper goes on to describe developments nearly identical to those summarized in the cited companion NASA Tech Briefs article, including the utilization of Boolean-satisfiability and integer- programming techniques to reduce the computation time and/or memory needed to solve the hitting-set problem.

Vatan, Farrokh↗

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↗

Introducing Tropical Geometric Approaches to Delay Tolerant Networking Optimization

Delay Tolerant Networking (DTN) is the standard approach to the networking of space systems with the goal of supporting the Solar System Internet (SSI). Current space networks have a small scale and often depend on rigorously scheduled (pre-determined) contact opportunities; this manual approach inhibits scalability. The goal of this paper is to recast these scheduling problems in order to apply the optimization machinery of tropical geometry. Contact opportunities in space are dependent on such factors as orbital mechanics and asset availability, which induce time-varying connectivity; indeed, end-to-end connectivity might never occur. Routing optimization within this structure is classically difficult and typically utilizes Dijkstra's algorithm as applied to contact graphs. Alternatively, we follow the successes of tropical geometry in train schedule optimization, job assignments, and even traditional networking, by extending this approach to this more general (i.e. disconnected) problem space. These successes imply tropical geometry provides a useful framework in the context of DTNs, starting with applications to queuing theory and long-haul links. Recently, tropical geometry has been applied to parametric path optimization on graphs with variable edge weights. In this work, we extend these advances to account for the problem of routing in a space network, and find that tropical geometry is well-suited to the challenges offered by this new setting, including contact schedules featuring probabilities. Our approach leverages the combinatorial nature of the problem to give feasible shortest path trees in the presence of variable channel conditions and latency, evolving topologies, and uncertainty inherent in space routing. We discuss our tropical approach to DTN for two Python implementations, a Verilog Tropical ALU implementation, tropical frameworks for other parametric graph problems, and solution stability. Lastly, a program for future work is included to illuminate the path ahead.

Delay Tolerant Networking↗

Machine Learning for Identifying Relevance to Biosurveillance in Multilingual Text

Objective: The objective is to develop an ensemble of machine learning algorithms to identify multilingual, online articles that are relevant to biosurveillance. Language morphology varies widely across languages and must be accounted for when designing algorithms. Here, we compare the performance of a word embedding-based approach and a topic modeling approach with machine learning algorithms to determine the best method for Chinese, Arabic, and French languages. Introduction: Global biosurveillance is an extremely important, yet challenging task. One form of global biosurveillance comes from harvesting open source online data (e.g. news, blogs, reports, RSS feeds). The information derived from this data can be used for timely detection and identification of biological threats all over the world. However, the more inclusive the data harvesting procedure is to ensure that all potentially relevant articles are collected, the more data that is irrelevant also gets harvested. This issue can become even more complex when the online data is in a non-native language. Foreign language articles not only create language-specific issues for Natural Language Processing (NLP), but also add a significant amount of translation costs. Previous work shows success in the use of combinatory monolingual classifiers in specific applications, e.g., legal domain [1]. A critical component for a comprehensive, online harvesting biosurveillance system is the capability to identify relevant foreign language articles from irrelevant ones based on the initial article information collected, without the additional cost of full text retrieval and translation.

Machine learning↗

Space communications scheduler: A rule-based approach to adaptive deadline scheduling

Job scheduling is a deceptively complex subfield of computer science. The highly combinatorial nature of the problem, which is NP-complete in nearly all cases, requires a scheduling program to intelligently transverse an immense search tree to create the best possible schedule in a minimal amount of time. In addition, the program must continually make adjustments to the initial schedule when faced with last-minute user requests, cancellations, unexpected device failures, quests, cancellations, unexpected device failures, etc. A good scheduler must be quick, flexible, and efficient, even at the expense of generating slightly less-than-optimal schedules. The Space Communication Scheduler (SCS) is an intelligent rule-based scheduling system. SCS is an adaptive deadline scheduler which allocates modular communications resources to meet an ordered set of user-specified job requests on board the NASA Space Station. SCS uses pattern matching techniques to detect potential conflicts through algorithmic and heuristic means. As a result, the system generates and maintains high density schedules without relying heavily on backtracking or blind search techniques. SCS is suitable for many common real-world applications.

Straguzzi, Nicholas↗

Machine Learning Applied to Zeolite Synthesis: The Missing Link for Realizing High-Throughput Discovery

Zeolites are microporous crystalline materials with well-defined cavities and pores, which can be prepared under different pore topologies and chemical compositions. Their preparation is typically defined by multiple interconnected variables (e.g., reagent sources, molar ratios, aging treatments, reaction time and temperature, among others), but unfortunately their distinctive influence, particularly on the nucleation and crystallization processes, is still far from being understood. Thus, the discovery and/or optimization of specific zeolites is closely related to the exploration of the parametric space through trial-and-error methods, generally by studying the influence of each parameter individually. In the past decade, machine learning (ML) methods have rapidly evolved to address complex problems involving highly nonlinear or massively combinatorial processes that conventional approaches cannot solve. Considering the vast and interconnected multiparametric space in zeolite synthesis, coupled with our poor understanding of the mechanisms involved in their nucleation and crystallization, the use of ML is especially timely for improving zeolite synthesis. Indeed, the complex space of zeolite synthesis requires drawing inferences from incomplete and imperfect information, for which ML methods are very well-suited to replace the intuition-based approaches traditionally used to guide experimentation. In this Account, we contend that both existing and new ML approaches can provide the “missing link” needed to complete the traditional zeolite synthesis workflow used in our quest to rationalize zeolite synthesis. Within this context, we have made important efforts on developing ML tools in different critical areas, such as (1) data-mining tools to process the large amount of data generated using high-throughput platforms; (2) novel complex algorithms to predict the formation of energetically stable hypothetical zeolites and guide the synthesis of new zeolite structures; (3) new “ab initio” organic structure directing agent predictions to direct the synthesis of hypothetical or known zeolites; (4) an automated tool for nonsupervised data extraction and classification from published research articles. ML has already revolutionized many areas in materials science by enhancing our ability to map intricate behavior to process variables, especially in the absence of well-understood mechanisms. Undoubtedly, ML is a burgeoning field with many future opportunities for further breakthroughs to advance the design of molecular sieves. For this reason, this Account includes an outlook of future research directions based on current challenges and opportunities. We envision this Account will become a hallmark reference for both well-established and new researchers in the field of zeolite synthesis.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Quantum Complexity of the Kronecker Coefficients

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP . This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA , complementing a recent NP -hardness result of Ikenmeyer, Mulmuley, and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Published by the American Physical Society 2024

Physics↗