21 |
Protein side-chain placement using CLPSwain, Martin T. January 2001 (has links)
Constraint logic programming (CLP) techniques can be used in protein side-chain placement, an important sub-task in comparative modelling. In a simple formulation values for domain variables represent rotamer side-chain conformations, and constraints represent atomic clashes. These constraints can be visualised using a "rotamer contact map", and observations made with this visualisation tool have been used to develop a strategy that overcomes limitations present in CLP caused by over-constrained residues. Null rotamers provide a mechanism that can automatically identify over-constrained residues. The use of null rotamers makes possible an iterative modelling strategy where, at each iteration, a CLP program is generated automatically; each program representing successively tighter packing constraints corresponding to larger atomic radii. Different CLP enumeration heuristics have been evaluated for use with this side-chain placement method, and it has been tested with several different rotamer libraries; a backbone-dependent rotamer library, when used with first-fail enumeration heuristics, was shown to be the most successful. Side-chain conformations predicted by this CLP method compare favourably against those predicted using other side-chain placement methods. The CLP method has been applied to two modelling problems. The first involved building models of class II MHC molecules in order to increase the utility of a peptide threading program. This program uses an allele's known or modelled 3D structure with a heuristic scoring function to predict peptides that are likely to bind to it - thus using CLP to model class II MHC alleles increases the program's utility. The second application used the CLP method to build structures of ribosome inactivating proteins (RIPs). These models were built using CLP together with comparative modelling approaches, and a model of bouganin, a recently identified wild RIF protein, has been built to help design engineered therapeutic proteins.
|
22 |
Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local SearchHe, Jun January 2013 (has links)
This thesis focuses on constraints for membership in formal languages under both the systematic search and stochastic local search approaches to constraint programming (CP). Such constraints are very useful in CP for the following three reasons: They provide a powerful tool for user-level extensibility of CP languages. They are very useful for modelling complex work shift regulation constraints, which exist in many shift scheduling problems. In the analysis, testing, and verification of string-manipulating programs, string constraints often arise. We show in this thesis that CP solvers with constraints for membership in formal languages are much more suitable than existing solvers used in tools that have to solve string constraints. In the stochastic local search approach to CP, we make the following two contributions: We introduce a stochastic method of maintaining violations for the regular constraint and extend our method to the automaton constraint with counters. To improve the usage of constraints for which there exists no known constant-time algorithm for neighbour evaluation, we introduce a framework of using solution neighbourhoods, and give an efficient algorithm of constructing a solution neighbourhood for the regular constraint. In the systematic search approach to CP, we make the following two contributions: We show that there may be unwanted consequences when using a propagator that may underestimate a cost of a soft constraint, as the propagator may guide the search to incorrect (non-optimum) solutions to an over-constrained problem. We introduce and compare several propagators that compute correctly the cost of the edit-distance based soft-regular constraint. We show that the context-free grammar constraint is useful and introduce an improved propagator for it.
|
23 |
Software verification and spatiotemporal aggregation in constraint databasesAnderson, Scot R. January 1900 (has links)
Thesis (Ph.D.)--University of Nebraska-Lincoln, 2007. / Title from title screen (site viewed Oct. 21, 2008). PDF text: ix, 149 p. : ill. (some col.) ; 2 Mb. UMI publication number: AAT 3321122. Includes bibliographical references. Also available in microfilm and microfiche formats.
|
24 |
Asynchrones Constraintlösen ein generisches Ausführungsmodell zur adaptiven, inkrementellen Constraintverarbeitung /Ringwelski, Georg. January 2003 (has links) (PDF)
Berlin, Techn. Univ., Diss., 2003.
|
25 |
Area and delay estimation for constraint-driven high-level synthesisNourani-Dargiri, Mehrdad January 1994 (has links)
No description available.
|
26 |
Les cohérences fortes : où, quand, et combien / Higher-Level Consistencies : When, Where, and How MuchWoodward, Robert J. 13 September 2018 (has links)
Déterminer si un problème de satisfaction de contraintes (CSP) a une solution ou non est NP-complet. Les CSP sont résolus par inférence (c’est-à-dire, en appliquant un algorithme de cohérence), par énumération (c’est-à-dire en effectuant une recherche avec retour sur trace ou backtracking), ou, plus souvent, en intercalant les deux mécanismes. La propriété de cohérence la plus courante appliquée en cours du backtracking est la GAC (Generalized Arc Consistency). Au cours des dernières années, de nouveaux algorithmes pour appliquer des cohérences plus fortes que le GAC ont été proposés et montrés comme étant nécessaires pour résoudre les problèmes difficiles.Nous nous attaquons à la question de balancer d’une part le coût et, d’autre part, le pouvoir d’élagage des algorithmes de cohérence et posons cette question comme étant celle de déterminer où, quand et combien une cohérence doit-elle être appliquée en cours de backtracking. Pour répondre à la question « où », nous exploitons la structure topologique d'une instance du problème et focalisons la cohérence forte là où des structures cycliques apparaissent. Pour répondre à la question « quand », nous proposons une stratégie simple, réactive et efficace qui surveille la performance du backtracking puis déclenche une cohérence forte lorsque l’effort du retour sur trace devient alarmant. Enfin, pour la question du « combien », nous surveillons les mises à jour provoquées par la propagation des contraintes et interrompons le processus dès qu’il devient inactif ou coûteux même avant qu’il n’atteigne un point fixe. Les évaluations empiriques sur des problèmes de référence établissent l’efficacité de nos stratégies. / Determining whether or not a Constraint Satisfaction Problem (CSP) has a solution is NP-complete. CSPs are solved by inference (i.e., enforcing consistency), conditioning (i.e., doing search), or, more commonly, by interleaving the two mechanisms. The most common consistency property enforced during search is Generalized Arc Consistency (GAC). In recent years, new algorithms that enforceconsistency properties stronger than GAC have been proposed and shown to be necessary to solve difficult problem instances.We frame the question of balancing the cost and the pruning effectiveness of consistency algorithms as the question of determining where, when, and how much of a higher-level consistency to enforce during search. To answer the ‘where’ question, we exploit the topological structure of a problem instance and target high-level consistency where cycle structures appear. To answer the ‘when’ question, we propose a simple, reactive, and effective strategy that monitors the performance of backtrack search and triggers a higher-level consistency as search thrashes. Lastly, for the question of ‘how much,’ we monitor the amount of updates caused by propagation and interrupt the process before it reaches a fixpoint. Empirical evaluations on benchmark problems demonstrate the effectiveness of our strategies.
|
27 |
Techniques for Efficient Constraint PropagationLagerkvist, Mikael Zayenz January 2008 (has links)
<p>This thesis explores three new techniques for increasing the efficiency of constraint propagation: support for incremental propagation, improved representation of constraints, and abstractions to simplify propagation. Support for incremental propagation is added to a propagator centered propagation system by adding a new intermediate layer of abstraction, advisors, that capture the essential aspects of a variable centered system. Advisors are used to give propagators a detailed view of the dynamic changes between propagator runs. Advisors enable the implementation of optimal algorithms for important constraints such as extensional constraints and Boolean linear in-equations, which is not possible in a propagator centered system lacking advisors. Using Multivalued Decision Diagrams (MDD) as the representation for extensional constraints is shown to be useful for several reasons. Classical operations on MDDs can be used to optimize the representation, and thus speeding up the propagation. In particular, the reduction operation is stronger than the use of DFA minimization for the regular constraint. The use of MDDs is contrasted and compared to a recent proposal where tables are compressed. Abstractions for constraint programs try to capture small and essential features of a model. These features may be much cheaper to propagate than the unabstracted program. The potential for abstraction is explored using several examples. These three techniques work on different levels. Support for incremental propagation is essential for the efficient implementation of some constraints, so that the algorithms have the right complexity. On a higher level, the question of representation looks at what a propagator should use for propagation. Finally, the question of abstraction can potentially look at several propagators, to find cases where abstractions might be fruitful. An essential feature of this thesis is a novel model for general placement constraints that uses regular expressions. The model is very versatile and can be used for several different kinds of placement problems. The model applied to the classic pentominoes puzzle will be used through-out the thesis as an example and for experiments.</p><p> </p> / <p>Den här avhandlingen utforskar tre nya tekniker för att öka effektiviteten av villkorspropagering: stöd för inkrementell propagering, val av representation för villkor, samt abstraktion för att förenkla propagering. Ett propageringssystem organiserat efter propagerare utökas med stöd för inkrementell propagering genom att lägga till ett nytt abstraktionslager: rådgivare. Detta lager fångar de essentiella aspekterna hos system organiserade efter variabler. Rådgivare används för att ge propagerare detaljerad information om de dynamiska ändringarna i variabler mellan körningar av propageraren. Utökningen innebär att det går att implementera optimala algoritmer för vissa viktiga villkor såsom tabellvillkor och Boolska linjära olikheter, något som inte är möjligt i ett rent propagator-organiserat system. Användandet av så kallade <em>Multivalued Decision Diagram</em> (MDD) som representation för tabellvillkor visas vara användbart i flera avseenden. Klassiska MDD-operationer kan användas för att optimera representationen, vilket leder till snabbare propagering. Specifikt så är reduktionsoperationen kraftfullare än användandet av DFA-minimering för reguljära villkor. MDD-representationen jämförs också med ett nyligen framlagt förslag för komprimerade tabeller. Abstraktioner för villkorsprogram försöker fånga små men viktiga egenskaper i modeller. Sådana egenskaper kan vara mycket enklare att propagera än den konkreta modellen. Potentialen för abstraktioner undersöks för några exempel. Dessa tre tekniker fungerar på olika nivåer. Stöd för inkrementell propagering är nödvändigt för att kunna implementera vissa villkor effektivt med rätt komplexitet. Valet av representation för villkor är på en högre nivå, då det gäller att se vilka algoritmer som skall användas för ett villkor. Slutligen så måste flera villkor i en modell studeras för att finna rätt typ av abstraktioner. Ett utmärkande drag för den här avhandlingen är en ny modell för generella placeringsvillkor som använder reguljära uttryck. Modellen är mångsidig och kan användas för flera olika typer av placeringsproblem. Modellen specialiserad för pentominopussel används genomgående som exempel för experiment.</p><p> </p> / Coordinating Constraint Propagation
|
28 |
Learning the Structure of Bayesian Networks with Constraint SatisfactionFast, Andrew Scott 01 February 2010 (has links)
A Bayesian network is graphical representation of the probabilistic relationships among set of variables and can be used to encode expert knowledge about uncertain domains. The structure of this model represents the set of conditional independencies among the variables in the data. Bayesian networks are widely applicable, having been used to model domains ranging from monitoring patients in an emergency room to predicting the severity of hailstorms. In this thesis, I focus on the problem of learning the structure of Bayesian networks from data. Under certain assumptions, the learned structure of a Bayesian network can represent causal relationships in the data. Constraint-based algorithms for structure learning are designed to accurately identify the structure of the distribution underlying the data and, therefore, the causal relationships. These algorithms use a series of conditional hypothesis tests to learn independence constraints on the structure of the model. When sample size is limited, these hypothesis tests are prone to errors. I present a comprehensive empirical evaluation of constraint-based algorithms and show that existing constraint-based algorithms are prone to many false negative errors in the constraints due to run- ning hypothesis tests with low statistical power. Furthermore, this analysis shows that many statistical solutions fail to reduce the overall errors of constraint-based algorithms. I show that new algorithms inspired by constraint satisfaction are able to produce significant improvements in structural accuracy. These constraint satisfaction algo- rithms exploit the interaction among the constraints to reduce error. First, I introduce an algorithm based on constraint optimization that is sound in the sample limit, like existing algorithms, but is guaranteed to produce a DAG. This new algorithm learns models with structural accuracy equivalent or better to existing algorithms. Second, I introduce an algorithm based constraint relaxation. Constraint relaxation combines different statistical techniques to identify constraints that are likely to be incorrect, and remove those constraints from consideration. I show that an algorithm combining constraint relaxation with constraint optimization produces Bayesian networks with significantly better structural accuracy when compared to existing structure learning algorithms, demonstrating the effectiveness of constraint satisfaction approaches for learning accurate structure of Bayesian networks.
|
29 |
Techniques for Efficient Constraint PropagationLagerkvist, Mikael Zayenz January 2008 (has links)
This thesis explores three new techniques for increasing the efficiency of constraint propagation: support for incremental propagation, improved representation of constraints, and abstractions to simplify propagation. Support for incremental propagation is added to a propagator centered propagation system by adding a new intermediate layer of abstraction, advisors, that capture the essential aspects of a variable centered system. Advisors are used to give propagators a detailed view of the dynamic changes between propagator runs. Advisors enable the implementation of optimal algorithms for important constraints such as extensional constraints and Boolean linear in-equations, which is not possible in a propagator centered system lacking advisors. Using Multivalued Decision Diagrams (MDD) as the representation for extensional constraints is shown to be useful for several reasons. Classical operations on MDDs can be used to optimize the representation, and thus speeding up the propagation. In particular, the reduction operation is stronger than the use of DFA minimization for the regular constraint. The use of MDDs is contrasted and compared to a recent proposal where tables are compressed. Abstractions for constraint programs try to capture small and essential features of a model. These features may be much cheaper to propagate than the unabstracted program. The potential for abstraction is explored using several examples. These three techniques work on different levels. Support for incremental propagation is essential for the efficient implementation of some constraints, so that the algorithms have the right complexity. On a higher level, the question of representation looks at what a propagator should use for propagation. Finally, the question of abstraction can potentially look at several propagators, to find cases where abstractions might be fruitful. An essential feature of this thesis is a novel model for general placement constraints that uses regular expressions. The model is very versatile and can be used for several different kinds of placement problems. The model applied to the classic pentominoes puzzle will be used through-out the thesis as an example and for experiments. / Den här avhandlingen utforskar tre nya tekniker för att öka effektiviteten av villkorspropagering: stöd för inkrementell propagering, val av representation för villkor, samt abstraktion för att förenkla propagering. Ett propageringssystem organiserat efter propagerare utökas med stöd för inkrementell propagering genom att lägga till ett nytt abstraktionslager: rådgivare. Detta lager fångar de essentiella aspekterna hos system organiserade efter variabler. Rådgivare används för att ge propagerare detaljerad information om de dynamiska ändringarna i variabler mellan körningar av propageraren. Utökningen innebär att det går att implementera optimala algoritmer för vissa viktiga villkor såsom tabellvillkor och Boolska linjära olikheter, något som inte är möjligt i ett rent propagator-organiserat system. Användandet av så kallade Multivalued Decision Diagram (MDD) som representation för tabellvillkor visas vara användbart i flera avseenden. Klassiska MDD-operationer kan användas för att optimera representationen, vilket leder till snabbare propagering. Specifikt så är reduktionsoperationen kraftfullare än användandet av DFA-minimering för reguljära villkor. MDD-representationen jämförs också med ett nyligen framlagt förslag för komprimerade tabeller. Abstraktioner för villkorsprogram försöker fånga små men viktiga egenskaper i modeller. Sådana egenskaper kan vara mycket enklare att propagera än den konkreta modellen. Potentialen för abstraktioner undersöks för några exempel. Dessa tre tekniker fungerar på olika nivåer. Stöd för inkrementell propagering är nödvändigt för att kunna implementera vissa villkor effektivt med rätt komplexitet. Valet av representation för villkor är på en högre nivå, då det gäller att se vilka algoritmer som skall användas för ett villkor. Slutligen så måste flera villkor i en modell studeras för att finna rätt typ av abstraktioner. Ett utmärkande drag för den här avhandlingen är en ny modell för generella placeringsvillkor som använder reguljära uttryck. Modellen är mångsidig och kan användas för flera olika typer av placeringsproblem. Modellen specialiserad för pentominopussel används genomgående som exempel för experiment. / QC 20101117 / Coordinating Constraint Propagation
|
30 |
Milao : a novel framework for mixed imperative and declarative formulation and solving of structural constraintsNarayanan, Vidya Priyadarshini 21 September 2010 (has links)
Advances in constraint solving and increases in processing power have enabled new
approaches for automating specification-based testing. However, writing specifications and
scaling techniques that utilize them remain challenging. We introduce Milao -- a novel
framework for mixed imperative and declarative formulation and solving of structural constraints
-- which addresses both these challenges. One, Milao introduces a mixed style for writing
specifications using a combination of declarative and imperative styles, which provides
flexibility in specification formulation and reduces its burden on the user. Two, it introduces a
mixed technique for solving constraints using a combination of solvers in synergy. As enabling
technologies, the Alloy tool-set and the Java PathFinder model checker are used. Initial
experiments witness the benefits of our framework. / text
|
Page generated in 0.0775 seconds