Dissertations / Theses on the topic 'Constraint satisfaction'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Constraint satisfaction.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Pang, Wanlin. "Constraint structure in constraint satisfaction problems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape10/PQDD_0012/NQ39165.pdf.
Full textBodirsky, Manuel. "Constraint satisfaction with infinite domains." Doctoral thesis, [S.l. : s.n.], 2004. http://deposit.ddb.de/cgi-bin/dokserv?idn=973605413.
Full textNightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.
Full textEngebretsen, Lars. "Approximate constraint satisfaction." Doctoral thesis, KTH, Numerical Analysis and Computer Science, NADA, 2000. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-2950.
Full textThornton, John Richard, and n/a. "Constraint Weighting Local Search for Constraint Satisfaction." Griffith University. School of Computing and Information Technology, 2000. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20050901.142439.
Full textThornton, John. "Constraint Weighting Local Search for Constraint Satisfaction." Thesis, Griffith University, 2000. http://hdl.handle.net/10072/367954.
Full textThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text
Thorstensen, Evgenij. "Hybrid tractability of constraint satisfaction problems with global constraints." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:05707b54-69e3-40eb-97e7-63b1a178c701.
Full textGharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.
Full textConstraint Programming (CP) is a powerful paradigm used for modelling and solving combinatorial constraint problems that relies on a wide range of techniques coming from artificial intelligence, operational research, graph theory,..., etc. The basic idea of constraint programming is that the user expresses its constraints and a constraint solver seeks a solution. Constraint Satisfaction Problems (CSP), is a framework at the heart of CP problems. They correspond to decision problems where we seek for states or objects satisfying a number of constraints or criteria. These decision problems have two answers to the question they encode: true, if the problem admits a solution, false, otherwise. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require the combination of heuristics and combinatorial optimization methods to solve them in a reasonable time.With the improvement of computers, larger and larger problems can be solved. However, the size of industrial problems grow faster which requires a vast amount of memory space to store them and entail great difficulties to solve them. In this thesis, our contributions can be divided into two main parts. In the first part, we deal with the most used kind of constraints, which are table constraints. We proposed two compressed forms of table constraints. Both of them are based on frequent patterns search in order to avoid redundancy. However, the manner of defining pattern, the patterns-detecting process and the new compact representation differ significantly. For each form, we propose a filtering algorithm. In the second part, we explore another way to optimize CSP solving which is the use of a parallel architecture. In fact, we enhance the solving process by establishing parallel consistencies. Different workers send to their master the result of establishing partial consistencies as new discovered facts. The master, in its turns tries to benefit from them by removing corresponding values
Fowler, David W. "Branching constraint satisfaction problems : sequential constrained decision making under uncertainty." Thesis, University of Aberdeen, 2002. http://digitool.abdn.ac.uk/R?func=search-advanced-go&find_code1=WSN&request1=AAIU153443.
Full textEgri, László. "The complexity of constraint satisfaction problems and symmetric Datalog /." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101843.
Full textIn recent years, logical and algebraic perspectives have been particularly successful in classifying CSPs. A major weapon in the arsenal of the logical perspective is the database-theory-inspired logic programming language called Datalog. A Datalog program can be used to solve a restricted class of CSPs by either accepting or rejecting a (suitably encoded) set of input constraints. Inspired by Dalmau's work on linear Datalog and Reingold's breakthrough that undirected graph connectivity is in logarithmic space, we use a new restriction of Datalog called symmetric Datalog to identify a class of CSPs solvable in logarithmic space. We establish that expressibility in symmetric Datalog is equivalent to expressibility in a specific restriction of second order logic called Symmetric Restricted Krom Monotone SNP that has already received attention for its close relationship with logarithmic space.
We also give a combinatorial description of a large class of CSPs lying in L by showing that they are definable in symmetric Datalog. The main result of this thesis is that directed st-connectivity and a closely related CSP cannot be defined in symmetric Datalog. Because undirected st-connectivity can be defined in symmetric Datalog, this result also sheds new light on the computational differences between the undirected and directed st-connectivity problems.
Martin, Barnaby D. "Logic, computation and constraint satisfaction." Thesis, University of Leicester, 2005. http://hdl.handle.net/2381/30530.
Full textDe, Vine Lance. "Analogical frames by constraint satisfaction." Thesis, Queensland University of Technology, 2020. https://eprints.qut.edu.au/198036/1/Lance_De%20Vine_Thesis.pdf.
Full textMiklos, Zoltan. "Understanding Tractable Decompositions for Constraint Satisfaction." Thesis, University of Oxford, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.491400.
Full textLee, David Alexander James. "Hybrid algorithms for distributed constraint satisfaction." Thesis, Robert Gordon University, 2010. http://hdl.handle.net/10059/509.
Full textTucker-Kellogg, Lisa 1969. "Systematic conformational search with constraint satisfaction." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/8081.
Full textIncludes bibliographical references (p. 170-177).
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, the bottleneck subchain(s) and therefore the whole search may be completed more efficiently. (2) A cost function evaluates alternative divide-and-conquer trees, provided that a preliminary OMNIMERGE search of the molecule has been completed. Then dynamic programming determines the optimal partitioning or "merge-tree" for the molecule; this merge-tree can be used to improve the efficiency of future searches.
(cont.) (3) PROPAGATION shares information by enforcing arc consistency between the solution sets of overlapping subchains. By filtering the solution set of each subchain, infeasible conformations are discarded rapidly. (4) An A* function prioritizes each subchain based on estimated future costs. Subchains with sufficiently low priority can be skipped, which improves efficiency. A common theme of these four ideas is to make good choices about how to break the large search problem into lower-dimensional subproblems. These novel algorithms were implemented and the effectiveness of each is demonstrated on a well-constrained peptide with 40 degrees of freedom.
by Lisa Tucker-Kellogg.
Ph.D.
Indurkhya, Sagar. "Acquiring minimalist grammars via constraint satisfaction." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/106114.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 77-78).
This thesis shows how to algorithmically construct a Minimalist Grammar lexicon that produces a specified set of MG derivations. This thesis introduces a mathematical structure, a Collection of Constraints, that captures the logical constraints, including those that arise as a consequence of the shortest move constraint, imposed upon the syntactic features of lexical items as they are merged together in a derivation produced by a given Minimalist Grammar lexicon. Methods are then developed that (a) map Minimalist Grammar lexicons to be Collections of Constraints, (b) map Collections of Constraints to Minimalist Grammar lexicons and (c) may combine two or more Collections of Constraints into a single Collection of Constraints. The thesis then demonstrates via a series of examples, framed as a simplified acquisition process, how these methods may be used together to iteratively construct a Minimalist Grammar lexicon starting from an empty Collection of Constraints and a sequence of Minimalist Grammar derivations, such that the constructed lexicon is able to generate the set of derivations.
by Sagar Indurkhya.
M. Eng.
Salamon, András Z. "Transformations of representation in constraint satisfaction." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:5d641fff-4d95-43b2-9ff8-73395d782ad8.
Full textMadelaine, Florent. "Constraint satisfaction problems and related logic." Thesis, University of Leicester, 2003. http://hdl.handle.net/2381/30524.
Full textFulla, Peter. "On the valued constraint satisfaction problem." Thesis, University of Oxford, 2018. http://ora.ox.ac.uk/objects/uuid:bb2491ef-d802-4c5d-a388-a042644a4b47.
Full textEscamocher, Guillaume. "Forbidden patterns in constraint satisfaction problems." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2283/.
Full textThe Constraint Satisfaction Problem (CSP) is NP-Complete, even in the case where all constraints are binary. However, some classes of CSP instances are tractable. Recently, a new method for defining such classes has emerged. This approach is centered around forbidden patterns, or the local absence of some conditions. It is the focus of my thesis. We formally define what forbidden patterns are, exhibit the properties they hold, and eventually put them to use in order to establish several important tractability results. Using different versions of patterns, all based on the same core concept, we list a significant number of new tractable classes, as well as some NP-Complete ones. We combine these results to reveal several dichotomies, each one encompassing a large range of classes of CSP instances. We also show how useful a tool forbidden patterns can be in the field of CSP instance simplification. We give multiple new ways of decreasing the size of CSP instances, whether by eliminating variables or fusioning domains, and prove how all these methods are enabled by the local absence of some patterns. Since the conditions for their use are entirely local, our operations can be used on a wide array of problems
Brown, Richard G. (Richard Gregory) Carleton University Dissertation Engineering Electrical. "An architecture for extending constraint satisfaction." Ottawa, 1991.
Find full textBlack, Daniel Peter. "Search in weighted constraint satisfaction problems." Thesis, University of Leeds, 2003. http://etheses.whiterose.ac.uk/1309/.
Full textCarbonnel, Clément. "Harnessing tractability in constraint satisfaction problems." Thesis, Toulouse, INPT, 2016. http://www.theses.fr/2016INPT0118/document.
Full textThe Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results
Van, Der Linden A. S. Janet. "Dynamic meta-constraints : an approach to dealing with non-standard constraint satisfaction problems." Thesis, Oxford Brookes University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.322242.
Full textKwaiter, Ghassan. "Modelisation declarative de scenes : etude ete realisation de solveurs de contraintes." Toulouse 3, 1998. http://www.theses.fr/1998TOU30242.
Full textLoewen, Nathan. "Conceptual design using probabilistic interval constraint satisfaction." Thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/14853.
Full textThornton, Anna C. "Constraint specification and satisfaction in embodiment design." Thesis, University of Cambridge, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.386171.
Full textNightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem." Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.
Full textBattle, Steven A. "A multiple representation approach to constraint satisfaction." Thesis, University of the West of England, Bristol, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.321835.
Full textWarwick, T. J. "A GA approach to constraint satisfaction problems." Thesis, University of Essex, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.260401.
Full textMagaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.
Full textGennari, Rosella. "Mapping Inferences: Constraint Propagation and Diamond Satisfaction." Diss., Universiteit van Amsterdam, 2002. http://hdl.handle.net/10919/71553.
Full textBudzynski, Louise. "Algorithmic barriers in random constraint satisfaction problems." Thesis, Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLE013.
Full textThe typical complexity of Constraint Satisfaction Problems (CSP) can be studied using random ensembles of instances. One observes threshold phenomena when the density of constraints increases, in particular a clustering phase transition at which typical solutions shatter into disconnected components. In this PhD, we introduce a bias that breaks the uniformity among solutions of a given instance of CSP, and look at the evolution of the clustering threshold under this bias, focusing on the bicoloring of k-uniform random hypergraphs. For small values of k, we show that this bias can delay the clustering transition to higher densities of constraints, and that it has a positive impact on the performances of Simulated Annealing algorithm to find a solution for a given instance of the bicoloring problem. In the large k limit, we compute the asymptotic expansion of the clustering threshold for the uniform and the biased measure, and characterize the gain obtained with our implementation of the bias
Judge, Mark. "Heuristically guided constraint satisfaction for AI planning." Thesis, University of Strathclyde, 2015. http://oleg.lib.strath.ac.uk:80/R/?func=dbin-jump-full&object_id=26615.
Full textGrant, Stuart Alexander. "Phase transition behaviour in constraint satisfaction problems." Thesis, University of Leeds, 1997. http://etheses.whiterose.ac.uk/1273/.
Full textCurtis, Suniel David. "Constraint satisfaction approaches to bus driver scheduling." Thesis, University of Leeds, 2000. http://etheses.whiterose.ac.uk/1287/.
Full textNguyen, Thi Hong Hiep. "Strong consistencies for weighted constraint satisfaction problems." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30004/document.
Full textThis thesis focuses on strong local consistencies for solving optimization problems in cost function networks (or weighted constraint networks). These methods provide the lower bound necessary for Branch-and-Bound search. We first study the Virtual arc consistency, one of the strongest soft arc consistencies, which is enforced by iteratively establishing hard arc consistency in a sequence of classical Constraint Networks. The algorithm enforcing VAC is improved by integrating the dynamic arc consistency to exploit its incremental behavior. The dynamic arc consistency also allows to improve VAC when maintained VAC during search by efficiently exploiting the changes caused by branching operations. Operations. Secondly, we are interested in stronger domain-based soft consistencies, inspired from similar consistencies in hard constraint networks (path inverse consistency, restricted or Max-restricted path consistencies). From each of these hard consistencies, many soft variants have been proposed for weighted constraint networks. The new consistencies provide lower bounds stronger than soft arc consistencies by processing triplets of variables connected two-by-two by binary cost functions. We have studied the properties of these new consistencies, implemented and tested them on a variety of problems
Cameron, Heather M. "Constraint satisfaction for interactive 3-D model acquisition." Thesis, University of British Columbia, 1990. http://hdl.handle.net/2429/28937.
Full textScience, Faculty of
Computer Science, Department of
Graduate
Padmanabhuni, Srinivas. "Logic programming with stable models for constraint satisfaction." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0009/NQ60011.pdf.
Full textHast, Gustav. "Beating a Random Assignment : Approximating Constraint Satisfaction Problems." Doctoral thesis, Stockholm, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-215.
Full textZhang, Lixi. "Solving the timetabling problem using constraint satisfaction programming." Access electronically, 2005. http://www.library.uow.edu.au/adt-NWU/public/adt-NWU20051104.155838/index.html.
Full textEgri, László. "The fine-grained complexity of constraint satisfaction problems." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=114132.
Full textLes problèmes de satisfaction de contraintes (ou CSP) forment un cadre particulièrement riche permettant de formaliser de façon uniforme un grand nombre de problèmes algorithmiques tirés de l'optimisation combinatoire, de l'intelligence artificielle et de la théorie des bases de données. À chaque domaine D et chaque langage de contraintes Γ (i.e. un ensemble de relations sur D), on associe le problème CSP(Γ) suivant. Une instance du problème est constituée d'une liste de variables x1,...,xn et d'une liste de contraintes de la forme (x7,x2,...,x5) ∈ R, où R ∈ Γ. On cherche à déterminer si des valeurs de D peuvent être assignées aux variables de telle sorte que les contraintes soient toutes satisfaites simultanément. La complexité algorithmique de CSP(Γ) est entièrement fonction de la structure du langage de contraintes Γ et on cherche alors à identifier des classes de contraintes pour lesquelles CSP(Γ) appartient à une classe de complexité spécifique. Récemment, la combinaison des approches logique et algébrique a porté fruits dans la compréhension de la complexité des CSP à l'intérieur de la classe P. En particulier, on a conjecturé des conditions algébriques nécessaires et suffisantes précises pour l'appartenance de CSP(Γ) dans les classes L et NL (sous les hypothèses habituelles en théorie de la complexité, e.g. L est différent de NL). Ces conditions algébriques sont sues être nécessaires, et d'un point de vue algorithmique, les indications en faveur du résultat s'accumulent rapidement. Les outils principaux pour établir l'appartenance d'un CSP à L ou NL sont respectivement les fragments "symmetric Datalog" et "linear Datalog" en programmation logique. Notre thèse est centrée sur la conjecture algébrique ci-haut mentionnée pour les CSP dans L, et la majeure partie du travail technique est dédiée à montrer l'appartenance de plusieurs grandes familles de CSP dans L. Entre autres résultats, nous caractérisons tous les graphes pour lesquels le problème de "list homomorphism" est dans L, une famille naturelle et bien étudiée de CSP. Nous étendons aussi ce résultat pour obtenir une caractérisation complète de la question pour les graphes. Nous développons de nouveaux outils (les dualités pour "symmetric Datalog") pour montrer l'appartenance de CSP dans L, nous prouvons une dichotomie L-NL pour les problèmes de "list homomorphism" pour les chemins orientés, nous donnons des résultats sur la structure et les polymorphismes des digraphes de Maltsev, et nous contribuons à la conjecture de Dalmau à l'effet que chaque CSP dans NL est en fait dans "linear Datalog".
Grayland, Andrews. "Automated static symmetry breaking in constraint satisfaction problems." Thesis, University of St Andrews, 2011. http://hdl.handle.net/10023/1718.
Full textAkatov, Dmitri. "Exploiting parallelism in decomposition methods for constraint satisfaction." Thesis, University of Oxford, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.531942.
Full textHoughton, Chris. "The effect of representations on constraint satisfaction problems." Thesis, University of London, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.603533.
Full textWu, Yi. "The Approximability of Learning and Constraint Satisfaction Problems." Research Showcase @ CMU, 2010. http://repository.cmu.edu/dissertations/24.
Full textKerrigan, Eric Colin. "Robust constraint satisfaction : invariant sets and predictive control." Thesis, University of Cambridge, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.621159.
Full textKim, Eun Jung. "Parameterized algorithms on digraph and constraint satisfaction problems." Thesis, Royal Holloway, University of London, 2010. http://repository.royalholloway.ac.uk/items/4e3a1971-6e98-97a9-8e4f-9e1fdc76066a/9/.
Full textLi, Yinghao. "Directed annealing search in constraint satisfaction and optimization." Thesis, Imperial College London, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.300251.
Full textLiu, Bing. "Reinforcement planning for resource allocation and constraint satisfaction." Thesis, University of Edinburgh, 1988. http://hdl.handle.net/1842/19055.
Full text