Página 1 dos resultados de 637 itens digitais encontrados em 0.023 segundos

A programming environment for on-demand service overlays

Agrawal, Rahul, 1980-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 50 p.; 2035915 bytes; 2035720 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
78.67437%
Recent years have seen a growing interest in overlay networks. Overlay networks simplify the complications of creating and connecting distributed applications on the network by optimizing the underlying IP routing architecture. This thesis presents a programming environment (PEON) for automatically generating, monitoring and adapting an overlay network in response to application requirements and changing network conditions. The system automatically generates and maintains an overlay of routing modules to satisfy the application requirements. The runtime environment employs various constraint-satisfaction-programming (CSP) heuristics to allocate resources between competing applications with varying requirements of bandwidth, latency, and packet loss. The system additionally offers a "Reflection API" that allows an application to monitor and adapt the internal structure of its overlay to fine-tune its parameters.; by Rahul Agrawal.; Thesis (M. Eng. and S.B.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.; Includes bibliographical references (p. 47).

Systematic conformational search with constraint satisfaction

Tucker-Kellogg, Lisa, 1969-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 178 p.; 13121395 bytes; 13121150 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
78.19385%
Determining the conformations of biological molecules is a high scientific priority for biochemists and for the pharmaceutical industry. This thesis describes a systematic method for conformational search, an application of the method to determining the structure of the formyl-Met-Leu-Phe-OH (fMLF)peptide by solid-state NMR spectroscopy, and a separate project to determine the structure of a protein-DNA complex by X-ray crystallography. The purpose of the systematic search method is to enumerate all conformations of a molecule (at a given level of torsion angle resolution) that satisfy a set of local geometric constraints. Constraints would typically come from NMR experiments, but applications such as docking or homology modelling could also give rise to similar constraints. The molecule to be searched is partitioned into small subchains so that the set of possible conformations for the whole molecule may be constructed by merging the feasible conformations for the parts. However, instead of using a binary tree for straightforward divide-and-conquer, four innovations are introduced: (1) OMNIMERGE searches a subproblem for every possible subchain of the molecule. Searching every subchain provides the advantage that every possible merge is available; by choosing the most favorable merge for each subchain...

Pseudonormality and a language multiplier theory for constrained optimization

Ozdaglar, Asuman E
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 213 leaves; 6986625 bytes; 6986431 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
68.9928%
Lagrange multipliers are central to analytical and computational studies in linear and non-linear optimization and have applications in a wide variety of fields, including communication, networking, economics, and manufacturing. In the past, the main research in Lagrange multiplier theory has focused on developing general and easily verifiable conditions on the constraint set, called constraint qualifications, that guarantee the existence of Lagrange multipliers for the optimization problem of interest. In this thesis, we present a new development of Lagrange multiplier theory that significantly differs from the classical treatments. Our objective is to generalize, unify, and streamline the theory of constraint qualifications. As a starting point, we derive an enahanced set of necessary optimality conditions of the Fritz John-type, which are stronger than the classical Karush-Kuhn-Tucker conditions. They are also more general in that they apply even when there is a possibly nonconvex abstract set constraint, in addition to smooth equality and inequality constraints. These optimality conditions motivate the introduction of a new condition, called pseudonormality, which emerges as central within the taxonomy of significant characteristics of a constraint set. In particular...

Programação por restrições aplicada a problemas de rearranjo de genomas; Constraint programming applied to genome rearrangement problems

Victor de Abreu Iizuka
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 19/12/2012 Português
Relevância na Pesquisa
89.13064%
A teoria da seleção natural de Darwin afirma que os seres vivos atuais descendem de ancestrais, e ao longo da evolução, mutações genéticas propiciaram o aparecimento de diferentes espécies de seres vivos. Muitas mutações são pontuais, alterando a cadeia de DNA, o que pode impedir que a informação seja expressa, ou pode expressá-la de um modo diferente. A comparação de sequências é o método mais usual de se identificar a ocorrência de mutações pontuais, sendo um dos problemas mais abordados em Biologia Computacional. Rearranjo de Genomas tem como objetivo encontrar o menor número de operações que transformam um genoma em outro. Essas operações podem ser, por exemplo, reversões, transposições, fissões e fusões. O conceito de distância pode ser definido para estes eventos, por exemplo, a distância de reversão é o número mínimo de reversões que transformam um genoma em outro [9] e a distância de transposição é o número mínimo de transposições que transformam um genoma em outro [10]. Nós trataremos os casos em que os eventos de reversão e transposição ocorrem de forma isolada e os casos quando os dois eventos ocorrem simultaneamente, com o objetivo de encontrar o valor exato para a distância. Nós criamos modelos de Programação por Restrições para ordenação por reversões e ordenação por reversões e transposições...

Applying integer programming techniques to find minimum integer weights of voting games

Strauss, Aaron B., 1980-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 76 p.; 3809395 bytes; 3817408 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
78.62489%
Using concepts from computer science and mathematics I develop three algorithms to find the minimum integer weights for voting games. Games with up to at least 17 players can be solved in a reasonable amount of time. First, coalitions are mapped to constraints, reducing the problem to constraint optimization. The optimization techniques used are Gomory's all-integer simplex algorithm and a variant of the popular integer programming method branch and bound. Theoretical results include that minimum integer weights are not unique and a confirmation of a prior result that minimum integer weights are proportional to a priori seat share. Thus, these algorithms can be useful for researchers evaluating the differences between proportional bargaining models and formateur models. The running times of the different algorithms are contrasted and analyzed for potential improvements.; by Aaron B. Strauss.; Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.; Includes bibliographical references (p. 73-76).

Domain Views for Constraint Programming

Van Hentenryck, Pascal; Michel, Laurent
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/01/2014 Português
Relevância na Pesquisa
69.364272%
Views are a standard abstraction in constraint programming: They make it possible to implement a single version of each constraint, while avoiding to create new variables and constraints that would slow down propagation. Traditional constraint-programming systems provide the concept of {\em variable views} which implement a view of the type $y = f(x)$ by delegating all (domain and constraint) operations on variable $y$ to variable $x$. This paper proposes the alternative concept of {\em domain views} which only delegate domain operations. Domain views preserve the benefits of variable views but simplify the implementation of value-based propagation. Domain views also support non-injective views compositionally, expanding the scope of views significantly. Experimental results demonstrate the practical benefits of domain views.; Comment: Workshop: TRICS13: Techniques foR Implementing Constraint programming, September 2013, CP, Uppsala

Integration of Declarative and Constraint Programming

Hofstedt, Petra; Pepper, Peter
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
69.175703%
Combining a set of existing constraint solvers into an integrated system of cooperating solvers is a useful and economic principle to solve hybrid constraint problems. In this paper we show that this approach can also be used to integrate different language paradigms into a unified framework. Furthermore, we study the syntactic, semantic and operational impacts of this idea for the amalgamation of declarative and constraint programming.; Comment: 30 pages, 9 figures, To appear in Theory and Practice of Logic Programming (TPLP)

Unsatisfiable Cores and Lower Bounding for Constraint Programming

Downing, Nicholas; Feydy, Thibaut; Stuckey, Peter J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/08/2015 Português
Relevância na Pesquisa
69.483423%
Constraint Programming (CP) solvers typically tackle optimization problems by repeatedly finding solutions to a problem while placing tighter and tighter bounds on the solution cost. This approach is somewhat naive, especially for soft-constraint optimization problems in which the soft constraints are mostly satisfied. Unsatisfiable-core approaches to solving soft constraint problems in SAT (e.g. MAXSAT) force all soft constraints to be hard initially. When solving fails they return an unsatisfiable core, as a set of soft constraints that cannot hold simultaneously. These are reverted to soft and solving continues. Since lazy clause generation solvers can also return unsatisfiable cores we can adapt this approach to constraint programming. We adapt the original MAXSAT unsatisfiable core solving approach to be usable for constraint programming and define a number of extensions. Experimental results show that our methods are beneficial on a broad class of CP-optimization benchmarks involving soft constraints, cardinality or preferences.

CPBVP: A Constraint-Programming Framework for Bounded Program Verification

Collavizza, Hélène; Rueher, Michel; Van Hentenryck, Pascal
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/07/2008 Português
Relevância na Pesquisa
69.53543%
This paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). The CPBPV framework uses constraint stores to represent the specification and the program and explores execution paths nondeterministically. The input program is partially correct if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraint programming to express the constraint store. Finally, CPBPV is parametrized with a list of solvers which are tried in sequence, starting with the least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs while other frameworks based on model checking have failed.

Towards non-threaded Concurrent Constraint Programming for implementing multimedia interaction systems

Toro, Mauricio
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/10/2015 Português
Relevância na Pesquisa
68.99427%
In this work we explain the implementation of event-driven real-time interpreters for the Concurrent Constraint Programming (CCP) and Non-deterministic Timed Concurrent Constraint (NTCC) for- malisms. The CCP interpreter was tested with a program to find, concurrently, paths in a graph and it will be used in the future to find musical sequences in the music improvisation software Omax, developed by the French Acoustics/Music Research Institute (IRCAM). In the other hand, the NTCC interpreter was tested with a music improvisation system based on NTCC (CCFOMI), developed by the AVISPA research group and IRCAM. Additionally, we present GECOL 2, a wrapper for the Generic Constraints Development Environment (GECODE) to Common LISP, de- veloped to port the interpreters to Common LISP in the future. We concluded that using GECODE for the concurrency control avoids the need of having threads and synchronizing them, leading to a simple and efficient implementation of CCP and NTCC. We also noticed that the time units in NTCC interpreter do not represent discrete time units, because when we simulate the NTCC specifications in the interpreter, the time units have different durations. In the future, we propose forcing the duration of each time unit to a fix time...

The Inductive Constraint Programming Loop

Bessiere, Christian; De Raedt, Luc; Guns, Tias; Kotthoff, Lars; Nanni, Mirco; Nijssen, Siegfried; O'Sullivan, Barry; Paparrizou, Anastasia; Pedreschi, Dino; Simonis, Helmut
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/10/2015 Português
Relevância na Pesquisa
69.414004%
Constraint programming is used for a variety of real-world optimisation problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current constraint programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming loop. In this approach data is gathered and analyzed systematically, in order to dynamically revise and adapt constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and constraint programming on the other hand.; Comment: 17 pages, 9 figures

Constraint-based sequence mining using constraint programming

Negrevergne, Benjamin; Guns, Tias
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
69.02804%
The goal of constraint-based sequence mining is to find sequences of symbols that are included in a large number of input sequences and that satisfy some constraints specified by the user. Many constraints have been proposed in the literature, but a general framework is still missing. We investigate the use of constraint programming as general framework for this task. We first identify four categories of constraints that are applicable to sequence mining. We then propose two constraint programming formulations. The first formulation introduces a new global constraint called exists-embedding. This formulation is the most efficient but does not support one type of constraint. To support such constraints, we develop a second formulation that is more general but incurs more overhead. Both formulations can use the projected database technique used in specialised algorithms. Experiments demonstrate the flexibility towards constraint-based settings and compare the approach to existing methods.; Comment: In Integration of AI and OR Techniques in Constraint Programming (CPAIOR), 2015

First-order Logic as a Constraint Programming Language

Apt, K. R.; Vermeulen, C. F. M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
68.978384%
We provide a denotational semantics for first-order logic that captures the two-level view of the computation process typical for constraint programming. At one level we have the usual program execution. At the other level an automatic maintenance of the constraint store takes place. We prove that the resulting semantics is sound with respect to the truth definition. By instantiating it by specific forms of constraint management policies we obtain several sound evaluation policies of first-order formulas. This semantics can also be used a basis for sound implementation of constraint maintenance in presence of block declarations and conditionals.; Comment: 17 pages. v2: improved version corrected reference to Turing (instead of Tarski)

Unsatisfiable Cores for Constraint Programming

Downing, Nicholas; Feydy, Thibaut; Stuckey, Peter J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/05/2013 Português
Relevância na Pesquisa
69.16639%
Constraint Programming (CP) solvers typically tackle optimization problems by repeatedly finding solutions to a problem while placing tighter and tighter bounds on the solution cost. This approach is somewhat naive, especially for soft-constraint optimization problems in which the soft constraints are mostly satisfied. Unsatisfiable-core approaches to solving soft constraint problems in Boolean Satisfiability (e.g. MAXSAT) force all soft constraints to hold initially. When solving fails they return an unsatisfiable core, as a set of soft constraints that cannot hold simultaneously. Using this information the problem is relaxed to allow certain soft constraint(s) to be violated and solving continues. Since Lazy Clause Generation (LCG) solvers can also return unsatisfiable cores we can adapt the MAXSAT unsatisfiable core approach to CP. We implement the original MAXSAT unsatisfiable core solving algorithms WPM1, MSU3 in a state-of-the-art LCG solver and show that there exist problems which benefit from this hybrid approach.; Comment: Submitted to CP2013

Qualitative Modelling via Constraint Programming: Past, Present and Future

Kelsey, Thomas W.; Kotthoff, Lars; Jefferson, Christoffer A.; Linton, Stephen A.; Miguel, Ian; Nightingale, Peter; Gent, Ian P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/09/2012 Português
Relevância na Pesquisa
69.41217%
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.; Comment: 15 pages plus references

Exploiting Semidefinite Relaxations in Constraint Programming

van Hoeve, Willem Jan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 16/07/2004 Português
Relevância na Pesquisa
69.24456%
Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.; Comment: 18 pages, 4 figures. Submitted preprint

A Proof Theoretic View of Constraint Programming

Apt, Krzysztof R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/10/1998 Português
Relevância na Pesquisa
69.175703%
We provide here a proof theoretic account of constraint programming that attempts to capture the essential ingredients of this programming style. We exemplify it by presenting proof rules for linear constraints over interval domains, and illustrate their use by analyzing the constraint propagation process for the {\tt SEND + MORE = MONEY} puzzle. We also show how this approach allows one to build new constraint solvers.; Comment: 25 pages

Explaining Constraint Programming

Apt, Krzysztof R.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/02/2006 Português
Relevância na Pesquisa
69.074053%
We discuss here constraint programming (CP) by using a proof-theoretic perspective. To this end we identify three levels of abstraction. Each level sheds light on the essence of CP. In particular, the highest level allows us to bring CP closer to the computation as deduction paradigm. At the middle level we can explain various constraint propagation algorithms. Finally, at the lowest level we can address the issue of automatic generation and optimization of the constraint propagation algorithms.; Comment: 15 pages, appeared in "Processes, Terms and Cycles: Steps on the Road to Infinity", (A. Middeldorp, V. van Oostrom, F. van Raamsdonk, R. de Vrijer, eds.), LNCS 3838, pp. 55-69. (2005)

Infinite Qualitative Simulations by Means of Constraint Programming

Apt, Krzysztof R.; Brand, Sebastian
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 02/08/2006 Português
Relevância na Pesquisa
69.26206%
We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations, we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraint programming system by drawing on ideas from bounded model checking. The resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects.; Comment: 15 pages; 12th International Conference on Principles and Practice of Constraint Programming (CP'06)

Constraint Programming viewed as Rule-based Programming

Apt, Krzysztof R.; Monfroy, Eric
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
69.591787%
We study here a natural situation when constraint programming can be entirely reduced to rule-based programming. To this end we explain first how one can compute on constraint satisfaction problems using rules represented by simple first-order formulas. Then we consider constraint satisfaction problems that are based on predefined, explicitly given constraints. To solve them we first derive rules from these explicitly given constraints and limit the computation process to a repeated application of these rules, combined with labeling.We consider here two types of rules. The first type, that we call equality rules, leads to a new notion of local consistency, called {\em rule consistency} that turns out to be weaker than arc consistency for constraints of arbitrary arity (called hyper-arc consistency in \cite{MS98b}). For Boolean constraints rule consistency coincides with the closure under the well-known propagation rules for Boolean constraints. The second type of rules, that we call membership rules, yields a rule-based characterization of arc consistency. To show feasibility of this rule-based approach to constraint programming we show how both types of rules can be automatically generated, as {\tt CHR} rules of \cite{fruhwirth-constraint-95}. This yields an implementation of this approach to programming by means of constraint logic programming. We illustrate the usefulness of this approach to constraint programming by discussing various examples...