Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “cliques”

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.

48 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

The Evolution of Networks in Extreme and Isolated Environment

This article reports on the evolution of network structure as it relates to the formal and informal aspects of social roles in well bounded, isolated groups. Research was conducted at the Amundsen-Scott South Pole Station over a 3-year period. Data was collected on crewmembers' networks of social interaction and personal advice over each of the 8.5-month winters during a time of complete isolation. In addition, data was collected on informal social role structure (e.g., instrumental leadership, expressive leadership). It was hypothesized that development and maintenance of a cohesive group structure was related to the presence of and group consensus on various informal social roles. The study found that core-periphery structures (i.e., reflecting cohesion) in winter-over groups were associated with the presence of critically important informal social roles (e.g., expressive leadership) and high group consensus on such informal roles. On the other hand, the evolution of clique structures (i.e., lack of cohesion) were associated with the absence of critical roles and a lack of consensus on these roles, particularly the critically important role of instrumental leader.

Johnson, Jeffrey C.↗
NASA NTRS1999

Behavior and Performance on Long-Duration Spaceflights: Evidence from Analogue Environments

Analyses of data collected in Antarctica since 1963 were conducted to identify features of behavior and performance likely to occur during long-duration missions in space.The influence of mission duration and station latitude on POMS mood scores was examined in 450 American men and women who overwintered in Antarctica between 1991 and 1998. The influence of crewmember social characteristics, personality traits, interpersonal needs, and station environments on measures of behavior and performance at the end of the austral winter was examined in 657 American men who overwintered between 1963 and 1974. Both data sets were used to examine the influence of crew social structure on individual performance. Results: Seasonal variations in mood appear to be associated with the altered diurnal cycle and psychological segmentation of the mission. Concurrent measures of personality, interpersonal needs, and coping styles are better predictors of depressed mood and peer-supervisor performance evaluations than baseline measures because of the unique features of the station social and physical environments and the absence of resources typically used to cope with stress elsewhere. Individuals in crews with a clique structure report significantly more depression, anxiety, anger, fatigue and confusion than individuals in crews with a core-periphery structure. Depressed mood is inversely associated with severity of station physical environment, supporting the existence of a positive or "salutogenic" effect for individuals seeking challenging experiences in extreme environments.

Palinkas, Lawrence A.↗
NASA NTRS2005

Real-Time System Verification by Kappa-Induction

We report the first formal verification of a reintegration protocol for a safety-critical, fault-tolerant, real-time distributed embedded system. A reintegration protocol increases system survivability by allowing a node that has suffered a fault to regain state consistent with the operational nodes. The protocol is verified in the Symbolic Analysis Laboratory (SAL), where bounded model checking and decision procedures are used to verify infinite-state systems by k-induction. The protocol and its environment are modeled as synchronizing timeout automata. Because k-induction is exponential with respect to k, we optimize the formal model to reduce the size of k. Also, the reintegrator's event-triggered behavior is conservatively modeled as time-triggered behavior to further reduce the size of k and to make it invariant to the number of nodes modeled. A corollary is that a clique avoidance property is satisfied.

Pike, Lee S.↗
NASA NTRS2009

Developing Large-Scale Bayesian Networks by Composition: Fault Diagnosis of Electrical Power Systems in Aircraft and Spacecraft

In this paper, we investigate the use of Bayesian networks to construct large-scale diagnostic systems. In particular, we consider the development of large-scale Bayesian networks by composition. This compositional approach reflects how (often redundant) subsystems are architected to form systems such as electrical power systems. We develop high-level specifications, Bayesian networks, clique trees, and arithmetic circuits representing 24 different electrical power systems. The largest among these 24 Bayesian networks contains over 1,000 random variables. Another BN represents the real-world electrical power system ADAPT, which is representative of electrical power systems deployed in aerospace vehicles. In addition to demonstrating the scalability of the compositional approach, we briefly report on experimental results from the diagnostic competition DXC, where the ProADAPT team, using techniques discussed here, obtained the highest scores in both Tier 1 (among 9 international competitors) and Tier 2 (among 6 international competitors) of the industrial track. While we consider diagnosis of power systems specifically, we believe this work is relevant to other system health management problems, in particular in dependable systems such as aircraft and spacecraft. (See CASI ID 20100021910 for supplemental data disk.)

Mengshoel, Ole Jakob↗
NASA NTRS2009

Developing Large-Scale Bayesian Networks by Composition: Fault Diagnosis of Electrical Power Systems in Aircraft and Spacecraft

This CD contains files that support the talk (see CASI ID 20100021404). There are 24 models that relate to the ADAPT system and 1 Excel worksheet. In the paper an investigation into the use of Bayesian networks to construct large-scale diagnostic systems is described. The high-level specifications, Bayesian networks, clique trees, and arithmetic circuits representing 24 different electrical power systems are described in the talk. The data in the CD are the models of the 24 different power systems.

Mengshoel, Ole Jakob↗
NASA NTRS2010

Initialization and Restart in Stochastic Local Search: Computing a Most Probable Explanation in Bayesian Networks

For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary topologies. We also give a novel formalization of stochastic local search, with focus on initialization and restart, using probability theory and mixture models. Experimentally, we apply our methods to the problem of MPE computation, using a stochastic local search algorithm known as Stochastic Greedy Search. By carefully optimizing both initialization and restart, we reduce the MPE search time for application BNs by several orders of magnitude compared to using uniform at random initialization without restart. On several BNs from applications, the performance of Stochastic Greedy Search is competitive with clique tree clustering, a state-of-the-art exact algorithm used for MPE computation in BNs.

Mengshoel, Ole J.↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2020

Decomposition Algorithms for Scalable Quantum Annealing

The presented python code provides wrapper functions for two decomposition algorithms: One algorithm to decompose Maximum Clique problems and one to decompose Minimum Vertex Cover problems. The functions take as input a networkx graph object, and decompose either problem on the input graph recursively into subproblems such that the optimal solution can be constructed from the optimal solutions of both subproblems. The recursion ends as soon as the subproblems reach a pre-specified size limit by the user, and they can be solved using any method provided in advance by the user as external function. This includes exact solvers or an adiabatic quantum annealer.

Pelofske, Elijah↗
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 OSTI2023

Noise dynamics of quantum annealers: estimating the effective noise using idle qubits

Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗