Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

An event-based architecture for solving constraint satisfaction problems.

ABSTRACT: Constraint satisfaction problems are ubiquitous in many domains. They are typically solved using conventional digital computing architectures that do not reflect the distributed nature of many of these problems, and are thus ill-suited for solving them. Here we present a parallel analogue/digital hardware architecture specifically designed to solve such problems. We cast constraint satisfaction problems as networks of stereotyped nodes that communicate using digital pulses, or events. Each node contains an oscillator implemented using analogue circuits. The non-repeating phase relations among the oscillators drive the exploration of the solution space. We show that this hardware architecture can yield state-of-the-art performance on random SAT problems under reasonable assumptions on the implementation. We present measurements from a prototype electronic chip to demonstrate that a physical implementation of the proposed architecture is robust to practical non-idealities and to validate the theory proposed.

SUBMITTER: Mostafa H

PROVIDER: S-EPMC4686837 | biostudies-literature | 2015

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

An event-based architecture for solving constraint satisfaction problems.

Mostafa Hesham H Müller Lorenz K LK Indiveri Giacomo G

Nature communications 20151208

Constraint satisfaction problems are ubiquitous in many domains. They are typically solved using conventional digital computing architectures that do not reflect the distributed nature of many of these problems, and are thus ill-suited for solving them. Here we present a parallel analogue/digital hardware architecture specifically designed to solve such problems. We cast constraint satisfaction problems as networks of stereotyped nodes that communicate using digital pulses, or events. Each node ...[more]

PMID: 26642827

Similar Datasets

Solving Constraint Satisfaction Problems with Networks of Spiking Neurons.

Project description:Network of neurons in the brain apply-unlike processors in our current generation of computer hardware-an event-based processing strategy, where short pulses (spikes) are emitted sparsely by neurons to signal the occurrence of an event at a particular point in time. Such spike-based computations promise to be substantially more power-efficient than traditional clocked processing schemes. However, it turns out to be surprisingly difficult to design networks of spiking neurons that can solve difficult computational problems on the level of single spikes, rather than rates of spikes. We present here a new method for designing networks of spiking neurons via an energy function. Furthermore, we show how the energy function of a network of stochastically firing neurons can be shaped in a transparent manner by composing the networks of simple stereotypical network motifs. We show that this design approach enables networks of spiking neurons to produce approximate solutions to difficult (NP-hard) constraint satisfaction problems from the domains of planning/optimization and verification/logical inference. The resulting networks employ noise as a computational resource. Nevertheless, the timing of spikes plays an essential role in their computations. Furthermore, networks of spiking neurons carry out for the Traveling Salesman Problem a more efficient stochastic search for good solutions compared with stochastic artificial neural networks (Boltzmann machines) and Gibbs sampling.

| S-EPMC4811945 | biostudies-literature

Solving dynamic multi-objective problems with a new prediction-based optimization algorithm.

Project description:This paper proposes a new dynamic multi-objective optimization algorithm by integrating a new fitting-based prediction (FBP) mechanism with regularity model-based multi-objective estimation of distribution algorithm (RM-MEDA) for multi-objective optimization in changing environments. The prediction-based reaction mechanism aims to generate high-quality population when changes occur, which includes three subpopulations for tracking the moving Pareto-optimal set effectively. The first subpopulation is created by a simple linear prediction model with two different stepsizes. The second subpopulation consists of some new sampling individuals generated by the fitting-based prediction strategy. The third subpopulation is created by employing a recent sampling strategy, generating some effective search individuals for improving population convergence and diversity. Experimental results on a set of benchmark functions with a variety of different dynamic characteristics and difficulties illustrate that the proposed algorithm has competitive effectiveness compared with some state-of-the-art algorithms.

| S-EPMC8330920 | biostudies-literature

A constraint solving approach to model reduction by tropical equilibration.

Project description:Model reduction is a central topic in systems biology and dynamical systems theory, for reducing the complexity of detailed models, finding important parameters, and developing multi-scale models for instance. While singular perturbation theory is a standard mathematical tool to analyze the different time scales of a dynamical system and decompose the system accordingly, tropical methods provide a simple algebraic framework to perform these analyses systematically in polynomial systems. The crux of these methods is in the computation of tropical equilibrations. In this paper we show that constraint-based methods, using reified constraints for expressing the equilibration conditions, make it possible to numerically solve non-linear tropical equilibration problems, out of reach of standard computation methods. We illustrate this approach first with the detailed reduction of a simple biochemical mechanism, the Michaelis-Menten enzymatic reaction model, and second, with large-scale performance figures obtained on the http://biomodels.net repository.

| S-EPMC4260239 | biostudies-literature

Solving Math Problems Approximately: A Developmental Perspective.

Project description:Although solving arithmetic problems approximately is an important skill in everyday life, little is known about the development of this skill. Past research has shown that when children are asked to solve multi-digit multiplication problems approximately, they provide estimates that are often very far from the exact answer. This is unfortunate as computation estimation is needed in many circumstances in daily life. The present study examined 4th graders, 6th graders and adults' ability to estimate the results of arithmetic problems relative to a reference number. A developmental pattern was observed in accuracy, speed and strategy use. With age there was a general increase in speed, and an increase in accuracy mainly for trials in which the reference number was close to the exact answer. The children tended to use the sense of magnitude strategy, which does not involve any calculation but relies mainly on an intuitive coarse sense of magnitude, while the adults used the approximated calculation strategy which involves rounding and multiplication procedures, and relies to a greater extent on calculation skills and working memory resources. Importantly, the children were less accurate than the adults, but were well above chance level. In all age groups performance was enhanced when the reference number was smaller (vs. larger) than the exact answer and when it was far (vs. close) from it, suggesting the involvement of an approximate number system. The results suggest the existence of an intuitive sense of magnitude for the results of arithmetic problems that might help children and even adults with difficulties in math. The present findings are discussed in the context of past research reporting poor estimation skills among children, and the conditions that might allow using children estimation skills in an effective manner.

| S-EPMC4865172 | biostudies-literature

Strategies Used by Pet Dogs for Solving Olfaction-Based Problems at Various Distances.

Project description:The olfactory acuity of domestic dogs has been well established through numerous studies on trained canines, however whether untrained dogs spontaneously utilize this ability for problem solving is less clear. In the present paper we report two studies that examine what strategies family dogs use in two types of olfaction-based problems as well as their success at various distances. In Study 1, thirty dogs were tasked with distinguishing a target, either their covered owner (Exp 1) or baited food (Exp 2), from three visually identical choices at distances of 0m (touching distance), 1m, and 3m. There were nine consecutive trials for each target. We found that in Exp 1 the dogs successfully chose their owners over strangers at 0m and 1m, but not at 3m, where they used a win-stay strategy instead. In Exp 2 the dogs were only successful in choosing the baited pot at 0m. They used the win-stay strategy at 1m, but chose randomly at 3m. In Study 2, a different group of dogs was tested with their owners (Exp 1) and baited food (Exp 2) at just the 3m distance with two possible targets in 10-10 trials. In Exp 1 the dogs' overall performance was at chance level; however, when analyzed by trial, we noticed that despite tending to find their owners on the first trial, they generally switched to a win-stay strategy in subsequent trials, only to return to correctly choosing their owners based on olfaction in the later trials. In Exp 2, the dogs chose randomly throughout. We also found that dogs who relied on visual information in the warm-up trials were less successful in the olfaction-based test. Our results suggest that despite their ability to successfully collect information through olfaction, family dogs often prioritize other strategies to solve basic choice tasks.

| S-EPMC4503413 | biostudies-literature

Solving search problems by strongly simulating quantum circuits.

Project description:Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply that all problems in NP and #P could be solved in polynomial time.

| S-EPMC3565169 | biostudies-other

Computing minimal nutrient sets from metabolic networks via linear constraint solving.

Project description:BackgroundAs more complete genome sequences become available, bioinformatics challenges arise in how to exploit genome sequences to make phenotypic predictions. One type of phenotypic prediction is to determine sets of compounds that will support the growth of a bacterium from the metabolic network inferred from the genome sequence of that organism.ResultsWe present a method for computationally determining alternative growth media for an organism based on its metabolic network and transporter complement. Our method predicted 787 alternative anaerobic minimal nutrient sets for Escherichia coli K-12 MG1655 from the EcoCyc database. The program automatically partitioned the nutrients within these sets into 21 equivalence classes, most of which correspond to compounds serving as sources of carbon, nitrogen, phosphorous, and sulfur, or combinations of these essential elements. The nutrient sets were predicted with 72.5% accuracy as evaluated by comparison with 91 growth experiments. Novel aspects of our approach include (a) exhaustive consideration of all combinations of nutrients rather than assuming that all element sources can substitute for one another(an assumption that can be invalid in general) (b) leveraging the notion of a machinery-duplicating constraint, namely, that all intermediate metabolites used in active reactions must be produced in increasing concentrations to prevent successive dilution from cell division, (c) the use of Satisfiability Modulo Theory solvers rather than Linear Programming solvers, because our approach cannot be formulated as linear programming, (d) the use of Binary Decision Diagrams to produce an efficient implementation.ConclusionsOur method for generating minimal nutrient sets from the metabolic network and transporters of an organism combines linear constraint solving with binary decision diagrams to efficiently produce solution sets to provided growth problems.

| S-EPMC3644277 | biostudies-literature

Young children selectively seek help when solving problems.

Project description:There is strong evidence that children show selectivity in their reliance on others as sources of information, but the findings to date have largely been limited to contexts that involve factual information. The current experiments were designed to determine whether children might also show selectivity in their choice of sources within a problem-solving context. Children in two age groups (20-24 months and 30-36 months, total N=60) were presented with a series of conceptually difficult problem-solving tasks and were given an opportunity to interact with adult experimenters who were depicted as either good helpers or bad helpers. Participants in both age groups preferred to seek help from the good helpers. The findings suggest that even young children evaluate others with reference to their potential to provide help and use this information to guide their behavioral choices.

| S-EPMC3661754 | biostudies-literature

Solving molecular docking problems with multi-objective metaheuristics.

Project description:Molecular docking is a hard optimization problem that has been tackled in the past with metaheuristics, demonstrating new and challenging results when looking for one objective: the minimum binding energy. However, only a few papers can be found in the literature that deal with this problem by means of a multi-objective approach, and no experimental comparisons have been made in order to clarify which of them has the best overall performance. In this paper, we use and compare, for the first time, a set of representative multi-objective optimization algorithms applied to solve complex molecular docking problems. The approach followed is focused on optimizing the intermolecular and intramolecular energies as two main objectives to minimize. Specifically, these algorithms are: two variants of the non-dominated sorting genetic algorithm II (NSGA-II), speed modulation multi-objective particle swarm optimization (SMPSO), third evolution step of generalized differential evolution (GDE3), multi-objective evolutionary algorithm based on decomposition (MOEA/D) and S-metric evolutionary multi-objective optimization (SMS-EMOA). We assess the performance of the algorithms by applying quality indicators intended to measure convergence and the diversity of the generated Pareto front approximations. We carry out a comparison with another reference mono-objective algorithm in the problem domain (Lamarckian genetic algorithm (LGA) provided by the AutoDock tool). Furthermore, the ligand binding site and molecular interactions of computed solutions are analyzed, showing promising results for the multi-objective approaches. In addition, a case study of application for aeroplysinin-1 is performed, showing the effectiveness of our multi-objective approach in drug discovery.

| S-EPMC6272647 | biostudies-literature

Undergraduate Performance in Solving Ill-Defined Biochemistry Problems.

Project description:With growing interest in promoting skills related to the scientific process, we studied performance in solving ill-defined problems demonstrated by graduating biochemistry majors at a public, minority-serving university. As adoption of techniques for facilitating the attainment of higher-order learning objectives broadens, so too does the need to appropriately measure and understand student performance. We extended previous validation of the Individual Problem Solving Assessment (IPSA) and administered multiple versions of the IPSA across two semesters of biochemistry courses. A final version was taken by majors just before program exit, and student responses on that version were analyzed both quantitatively and qualitatively. This mixed-methods study quantifies student performance in scientific problem solving, while probing the qualitative nature of unsatisfactory solutions. Of the five domains measured by the IPSA, we found that average graduates were only successful in two areas: evaluating given experimental data to state results and reflecting on performance after the solution to the problem was provided. The primary difficulties in each domain were quite different. The most widespread challenge for students was to design an investigation that rationally aligned with a given hypothesis. We also extend the findings into pedagogical recommendations.

| S-EPMC5749965 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data