Dissertations / Theses on the topic 'Constraint satisfaction'
To see the other types of publications on this topic, follow the link: 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.
1
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 text
2
Bodirsky, Manuel. "Constraint satisfaction with infinite domains." Doctoral thesis, [S.l. : s.n.], 2004. http://deposit.ddb.de/cgi-bin/dokserv?idn=973605413.
Full text
3
Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.
Full text
4
Engebretsen, 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 text
5
Thornton, 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 textAbstract:
One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems
6
Thornton, John. "Constraint Weighting Local Search for Constraint Satisfaction." Thesis, Griffith University, 2000. http://hdl.handle.net/10072/367954.
Full textAbstract:
One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problemsThesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Science, Environment, Engineering and Technology
Full Text
7
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 textAbstract:
A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or intensionally, whether by an equation, propositional logic formula, or other means. Intensionally represented constraints, known as global constraints, are a powerful modelling technique, and many modern CSP solvers provide them. We give examples to show how problems that deal with product configuration can be modelled with such constraints, and how this approach relates to other modelling formalisms. The complexity of CSPs with extensionally represented constraints is well understood, and there are several known techniques that can be used to identify tractable classes of such problems. For CSPs with global constraints, however, many of these techniques fail, and far fewer tractable classes are known. In order to remedy this state of affairs, we undertake a systematic review of research into the tractability of CSPs. In particular, we look at CSPs with extensionally represented constraints in order to understand why many of the techniques that give tractable classes for this case fail for CSPs with global constraints. The above investigation leads to two discoveries. First, many restrictions on how the constraints of a CSP interact implicitly rely on a property of extensionally represented constraints to guarantee tractability. We identify this property as being a bound on the number of solutions in key parts of the instance, and find classes of global constraints that also possess this property. For such classes, we show that many known tractability results apply. Furthermore, global constraints allow us to treat entire CSP instances as constraints. We combine this observation with the above result, and obtain new tractable classes of CSPs by dividing a CSP into smaller CSPs drawn from known tractable classes. Second, for CSPs that simply do not possess the above property, we look at how the constraints of an instance overlap, and how assignments to the overlapping parts extend to the rest of the problem. We show that assignments that extend in the same way can be identified. Combined with a new structural restriction, this observation leads to a second set of tractable classes. We conclude with a summary, as well as some observations about potential for future work in this area.
8
Gharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.
Full textAbstract:
La programmation par contraintes est un cadre puissant utilisé pour modéliser et résoudre des problèmes combinatoires, employant des techniques d'intelligence artificielle, de la recherche opérationnelle, de théorie des graphes,..., etc. L'idée de base de la programmation par contraintes est que l'utilisateur exprime ses contraintes et qu'un solveur de contraintes cherche une ou plusieurs solutions.Les problèmes de satisfaction de contraintes (CSP), sont au cœur de la programmation par contraintes. Ce sont des problèmes de décision où nous recherchons des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Ces problèmes de décision revoient vrai, si le problème admet une solution, faux, sinon. Les problèmes de satisfaction de contraintes sont le sujet de recherche intense tant en recherche opérationnelle qu'en intelligence artificielle. Beaucoup de CSPs exigent la combinaison d'heuristiques et de méthode d'inférences combinatoires pour les résoudre dans un temps raisonnable.Avec l'amélioration des ordinateurs, la résolution de plus grands problèmes devient plus facile. Bien qu'il y ait plus de capacités offertes par la nouvelle génération de machines, les problèmes industriels deviennent de plus en plus grand ce qui implique un espace _norme pour les stocker et aussi plus de temps pour les résoudre.Cette thèse s'articule autour des techniques d'optimisation de la résolution des CSPs en raisonnant sur plusieurs axes.Dans la première partie, nous traitons la compression des contraintes table. Nous proposons deux méthodes différentes pour la compression des contraintes de table. Les deux approches sont basées sur la recherche des motifs fréquents pour éviter la redondance. Cependant, la façon de définir un motif, la détection des motifs fréquents et la nouvelle représentation compacte diffère significativement. Nous présentons pour chacune des approches un algorithme de filtrage.La seconde partie est consacrée à une autre façon d'optimiser la résolution de CSP qui est l'utilisation d'une architecture parallèle. Nous proposons une méthode où nous utilisons une architecture parallèle pour améliorer le processus de résolution en établissant des cohérences parallèles. En fait, les esclaves envoient à leur maître le résultat obtenu après avoir établi la cohérence partielle en tant que nouveaux faits. Le maître, à son tour essaye de profiter d'eux en enlevant les valeurs correspondantesConstraint 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
9
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 textAbstract:
One of the main characteristics of our world is uncertainty. Making plans for the future is difficult, as we do not know exactly what the future holds. Companies must be flexible, ready to cope with the unpredictable demands that are placed on them. As a result, plans are often either short term, or tend to change soon after they are made. Another feature of the modern world is its pace. Decisions must be made quickly, or events may make them out of date before they can be implemented. In this thesis, we look at decision making problems in the presence of uncertainty about how the problem may develop over time, and in particular where the decisions must be made efficiently. Constraint based reasoning has proven to be a very successful technique for supporting decision making, but to date it has assumed static problems. In this thesis, we will show that constraint based methods can be used to reason about uncertain futures, and we will present a method which incorporates some ideas from decision theory to represent and solve such problems. In particular, we will formulate a class of problems, develop systematic optimisation search techniques, incomplete heuristic methods and compare with existing techniques.
10
Egri, 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 textAbstract:
Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1, x2,..., x n and a list of constraints of the form "(x 7, x2,..., x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class.In 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.
11
Martin, Barnaby D. "Logic, computation and constraint satisfaction." Thesis, University of Leicester, 2005. http://hdl.handle.net/2381/30530.
Full textAbstract:
We study a class of non-deterministic program schemes with while loops: firstly, augmented with a priority queue for memory; secondly, augmented with universal quantification; and, thirdly, augmented with universal quantification and a stack for memory. We try to relate these respective classes of program schemes to well-known complexity classes and logics.;We study classes of structure on which path system logic coincides with polynomial time P.;We examine the complexity of generalisations of non-uniform boolean constraint satisfaction problems, where the inputs may have a bounded number of quantifier alternations (as opposed to the purely existential quantification of the CSP). We prove, for all bounded-alternation prefixes that have some universal quantifiers to the outside of some existential quantifiers (i.e. 2 and above), that this generalisation of boolean CSP respects the same dichotomy as that for the non-uniform boolean quantified constraint satisfaction problem.;We study the non-uniform QCSP, especially on digraghs, through a combinatorial analog - the alternating-homomorphism problem - that sits in relation to the QCSP exactly as the homomorphism problem sits with the CSP. We establish a trichotomy theorem for the non-uniform QCSP when the template is restricted to antireflexive, undirected graphs with at most one cycle. Specifically, such templates give rise to QCSPs that are either tractable, NP-complete or Pspace-complete.;We study closure properties on templates that respect QCSP hardness or QCSP equality. Our investigation leads us to examine the properties of first-order logic when deprived of the equality relation.;We study the non-uniform QCSP on tournament templates, deriving sufficient conditions for tractablity, NP-completeness and Pspace-completeness. In particular, we prove that those tournament templates that give rise to tractable CSP also give rise to tractable QCSP.
12
De, 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 textAbstract:
This research develops a new and efficient constraint satisfaction approach to the unsupervised discovery of linguistic analogies. It shows that systems of analogies can be discovered with high confidence in natural language text by a computer program without human input. The discovery of analogies is useful for many applications such as the construction of linguistic resources, natural language processing and the automation of inference and reasoning.
13
Miklos, Zoltan. "Understanding Tractable Decompositions for Constraint Satisfaction." Thesis, University of Oxford, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.491400.
Full textAbstract:
Constraint satisfaction problems (CSPs) are NP-complete in general, therefore it is important to identify tractable subclasses. A possible way to find such subclasses is to associate a hypergraph to the problem and impose restrictions on its structure. In this thesis we follow this direction. Among such structural properties, particularly important is acyclicity: it is well known that CSPs whose associated hypergraph is acyclic can be solved efficiently. In the last decade, many structural decompositions have been proposed. These concepts can be seen as generalizations of hypergraph acyclicity. The interesting decomposition concepts· are those which both enable the problems in the defined subclass to be solved in polynomial time and the associated hypergraphs to be recognized efficiently. Hypertree decompositions, introduced by Gottlob et al. in 2002, fall in this category and additionally, for a long time, this class was the most general concept known to have both of these desirable properties. We study further generalizations of this concept. It was shown recently by Gottlob et al. in 2007, that the recognition problem for the most straightforward generalization, for the so called generalized hypertree decompositions, is NP-hard. Understanding the deep reasons for this intractability result enabled us to define new decompositions with tractable recognition algorithms. We not only introduce a new decomposition concept, but also a methodology to define such decompositions using subedges of the hypergraph. In this way we get a very cle~r picture of tractable decompositions. As an application of our method, we construct a new decomposition concept, called component hypertree decomposition, which is tractable and strictly more general than all other known tractable methods, including the recently introduced spread cut decomposition. We also define an eV,en more general concept, which also generalizes the spread cut decompositions, according to their new definitions. We analyze various properties of generalized hypertree decompositions and study the parallel complexity of the recognition algorithms for the known tractable decomposition methods. Understanding their similarities and their relation to generalized hypertree decomposition, we gave upper bounds for the parallel complexity of their recognition.
14
Lee, David Alexander James. "Hybrid algorithms for distributed constraint satisfaction." Thesis, Robert Gordon University, 2010. http://hdl.handle.net/10059/509.
Full textAbstract:
A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP which is divided into several inter-related complex local problems, each assigned to a different agent. Thus, each agent has knowledge of the variables and corresponding domains of its local problem together with the constraints relating its own variables (intra-agent constraints) and the constraints linking its local problem to other local problems (inter-agent constraints). DisCSPs have a variety of practical applications including, for example, meeting scheduling and sensor networks. Existing approaches to Distributed Constraint Satisfaction can be mainly classified into two families of algorithms: systematic search and local search. Systematic search algorithms are complete but may take exponential time. Local search algorithms often converge quicker to a solution for large problems but are incomplete. Problem solving could be improved through using hybrid algorithms combining the completeness of systematic search with the speed of local search. This thesis explores hybrid (systematic + local search) algorithms which cooperate to solve DisCSPs. Three new hybrid approaches which combine both systematic and local search for Distributed Constraint Satisfaction are presented: (i) DisHyb; (ii) Multi-Hyb and; (iii) Multi-HDCS. These approaches use distributed local search to gather information about difficult variables and best values in the problem. Distributed systematic search is run with a variable and value ordering determined by the knowledge learnt through local search. Two implementations of each of the three approaches are presented: (i) using penalties as the distributed local search strategy and; (ii) using breakout as the distributed local search strategy. The three approaches are evaluated on several problem classes. The empirical evaluation shows these distributed hybrid approaches to significantly outperform both systematic and local search DisCSP algorithms. DisHyb, Multi-Hyb and Multi-HDCS are shown to substantially speed-up distributed problem solving with distributed systematic search taking less time to run by using the information learnt by distributed local search. As a consequence, larger problems can now be solved in a more practical timeframe.
15
Tucker-Kellogg, Lisa 1969. "Systematic conformational search with constraint satisfaction." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/8081.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.Includes 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.
16
Indurkhya, Sagar. "Acquiring minimalist grammars via constraint satisfaction." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/106114.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged 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.
17
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 textAbstract:
In this thesis I study constraint satisfaction problems or CSPs. These require determining whether values can be assigned to variables so that all constraints are satisfied. An important challenge is to identify tractable CSPs which can be solved efficiently. CSP instances have usually been grouped together by restricting either the allowed combinations of values, or the way the variables are allowed to interact. Such restrictions sometimes yield tractable CSPs. A weakness of this method is that it cannot explain why all-different constraints form a tractable CSP. In this common type of constraint, all variables must be assigned values that are different from each other. New techniques are therefore needed to explain why such CSPs can be solved efficiently. My main contribution is an investigation of such hybrid CSPs which cannot be defined with either one of these kinds of restrictions. The main technique I use is a transformation of a CSP instance to the microstructure representation. This represents an instance as a collection of sets, and a solution of the instance corresponds to an independent set in the clause structure. For the common case where all constraints involve only two variables, I show how the microstructure can be used to define CSPs that are tractable because their clause structures fall within classes of graphs for which an independent set of specified size can be found efficiently. Such tractable hereditary classes are defined by using the technique of excluded induced subgraphs, such as classes of graphs that contain neither odd cycles with five or more vertices, nor their complements. I also develop finer grained techniques, by allowing vertices of the microstructure representation to be assigned colours, and the variables to be ordered. I show that these techniques define a new tractable CSP that forbids an ordered vertex-coloured subgraph in the microstructure representation.
18
Madelaine, Florent. "Constraint satisfaction problems and related logic." Thesis, University of Leicester, 2003. http://hdl.handle.net/2381/30524.
Full textAbstract:
Feder and Vardi have proved that the class captured by a monadic fragment of existential second-order logic, MMSNP, is computationally equivalent (via randomised reductions) to the class of constraint satisfaction problems (CSP) while the latter is strictly included in the former. I introduce a new class of combinatorial problems, the so-called forbidden patterns problems (FP), that correspond exactly to the logic MMSNP and introduce some novel algebraic tools like the re-colouring that allow me to construct a normal form. This leads to a constructive characterisation of the borderline of CSP within FP: a given problem in FP is either given as a problem in CSP or we build counter-examples. I relate this result to a recent and independent work by Tardif and Nesetril which relies heavily on a correspondence between duality and density. I generalise this approach to FP. Finally, I investigate homomorphism problems for unary algebras.
19
Fulla, 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 textAbstract:
The Valued Constraint Satisfaction Problem (VCSP) is a framework which captures many natural decision and optimisation problems. An instance of the VCSP consists of a set of variables, which are to be assigned labels from a finite domain, and a collection of local constraints, each specified by a weighted relation mapping labellings of the variables in the constraint's scope to values. The objective is to minimise the total value from all constraints. The VCSP is commonly parameterised by a language, i.e. a set of weighted relations that are available for use in the constraints. Languages are classified according to the computational complexity of the VCSP as tractable, for which the problem can be solved in polynomial time, and intractable, for which the problem is NP-hard. The recently proved VCSP dichotomy theorem established a classification of all languages into these two categories. Additionally, various structural restrictions can be imposed to limit the set of admissible instances further, thus potentially changing the complexity of the VCSP. Our first contribution relates to the algebraic approach to the VCSP, which proved instrumental in recent advances in the field. We generalise the Galois connection between weighted relational clones and weighted clones so that it applies to infinite sets as well. Second, we study a structural restriction requiring that the incidence graph be planar. In this setting, we establish a complexity classification of conservative languages (i.e. languages containing all {0,1}-valued unary weighted relations) and a necessary tractability condition for Boolean languages (i.e. languages over a two-element domain). Third, we study the surjective variant of the VCSP, in which labellings are required to assign every domain element to at least one variable. We establish a complexity classification of Boolean languages, which encompasses a new tractable class of problems.
20
Escamocher, Guillaume. "Forbidden patterns in constraint satisfaction problems." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2283/.
Full textAbstract:
Le problème de satisfaction de contraintes (CSP) est NP-complet, même dans le cas où toutes les contraintes sont binaires. Cependant, certaines classes d'instances CSP sont traitables. Récemment, une nouvelle méthode pour définir de telles classes aémergée. Cette approche est centrée autour des motifs interdits, ou l'absence locale de certaines conditions. Elle est l'objet de ma thèse. Nous définissons formellement ce que sont les motifs interdits, présentons les propriétés qu'ils détiennent, et finalement les utilisons afin d'établir plusieurs résultats de complexité importants. En utilisant différentes versions de motifs, toutes basées sur le même concept de base, nous énumérons un nombre important de nouvelles classes traitables, ainsi que certaines NP-completes. Nous combinons ces résultats pour révéler plusieurs dichotomies, chacune englobant une large gamme de classes d'instances CSP. Nous montrons aussi que les motifs interdits représentent un outil intéressant pour la simplification d'instances CSPs. Nous donnons plusieurs nouveaux moyens de réduire la taille des instances CSP, que ce soit en éliminant des variables ou en fusionnant les domaines, et montrons comment ces méthodes sont activées par l'absence locale de certains modèles. Comme les conditions de leurutilisation sont entièrement locales, nos opérations peuvent être utilisés sur un large éventail de problèmesThe 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
21
Brown, Richard G. (Richard Gregory) Carleton University Dissertation Engineering Electrical. "An architecture for extending constraint satisfaction." Ottawa, 1991.
Find full text
22
Black, Daniel Peter. "Search in weighted constraint satisfaction problems." Thesis, University of Leeds, 2003. http://etheses.whiterose.ac.uk/1309/.
Full textAbstract:
A wide variety of real-world optimisation problems can be modelled as Weighted Constraint Satisfaction Problems (WCSPs). Such problems are NP-hard and require an exponential amount of time to find the optimal solution. This thesis concentrates on the University Examination Timetabling Problem. A general abstraction of this problem has been used, as there are many institution-specific rules which could be incorporated into the problem. The use of this problem type allows WCSPs to be investigated using realistic problem data and allows a comparison with previously published results for the problem instances used. We have examined some existing variable ordering heuristics and defined new ones. An analysis methodology has been defined that allows the characteristics of good solutions to be identified. Different methods of identifying difficult to solve sub-problems and the use of such methods in variable ordering has been investigated. Incorporating the weight, or preference, associated with constraints into variable ordering heuristics has been found to be beneficial to finding solutions of low cost. The analysis methodology has been used to examine the relationship between solutions of different quality and the knowledge derived has been used to define, and justify, two new variable ordering heuristics. The usefulness of different value ordering heuristics has been examined. Value selection on the error incurred with past assignments and the use of look-ahead have been investigated. Variable ordering heuristics have been extended to try and exploit the advantages of such value ordering heuristics. The use of stochasticity with such orderings has been investigated and has led to a new class of hybrid value ordering heuristics being defined. Finally two hybrid search algorithms have been defined that attempt to concentrate search upon the sections of the problem instance which have the largest effect upon the overall quality of solutions found. Such methods are shown to be at least competitive with standard tree based search techniques.
23
Carbonnel, Clément. "Harnessing tractability in constraint satisfaction problems." Thesis, Toulouse, INPT, 2016. http://www.theses.fr/2016INPT0118/document.
Full textAbstract:
Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteusesThe 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
24
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 text
25
Kwaiter, Ghassan. "Modelisation declarative de scenes : etude ete realisation de solveurs de contraintes." Toulouse 3, 1998. http://www.theses.fr/1998TOU30242.
Full textAbstract:
De nombreuses recherches sont menees dans le domaine de la modelisation declarative, mais de nombreux problemes restent a resoudre : la notion de contrainte comme moyen de description, et celle de solveur pour maintenir les modeles decrits ne sont pas suffisamment distinctes ; la detection des incoherences et des contradictions entre les contraintes generees par le modeleur, les possibilites de reduire le nombre de solutions produites par l'ajout incremental de contraintes ou par la modification de priorites de contraintes, les possibilites de decrire la scene dynamiquement, par ajout et suppression de contraintes ou par ajout et suppression d'objets contraints ont ete peu explorees et constituent une nouvelle maniere de resoudre ce type de probleme. Notre contribution principale dans ce memoire se situe dans le cadre de la modelisation declarative par contraintes. Nous avons etudie et developpe un solveur de contraintes nomme oranos qui s'appuie, dans sa conception, sur l'approche csp (constraint satisfaction problems). Oranos offre un modele etendu de csp : dhncsp (dynamical, hierachical, numerical csp). Ce modele decoule en fait de deux domaines independants de recherche dans l'intelligence artificielle : les contraintes hierarchiques et les contraintes dynamiques. Le premier domaine offre une solution efficace aux problemes sur-contraints et le deuxieme permet de developper une application interactive. Notre solveur oranos a ete utilise pour une application de placement d'objets dans une scene tridimensionnelle par description de la scene grace a un ensemble de contraintes. Les approches precedentes ont considere le probleme avec des points de vue distincts et parfois divergents, en s'interessant principalement a la geometrie. Nous avons choisi de rester tres general au niveau du solveur afin de pouvoir utiliser les memes concepts dans des applications semblables. Nous considerons ainsi que l'originalite et l'interet de notre approche reside dans la prise en compte des aspects dynamiques, hierarchiques et declaratifs, ouvrant ainsi une nouvelle voie vers une conception d'applications interactives plus proches du concepteur. Ceci etant obtenu par une plus grande cooperation entre le concepteur et le systeme.
26
Loewen, Nathan. "Conceptual design using probabilistic interval constraint satisfaction." Thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/14853.
Full textAbstract:
Dealing with uncertainty is one of the primary challenges engineers face in the conceptual design phase of a project. Engineers must make decisions with regards to uncertain design parameters that influence performance and cost. It is well recognized that decisions made in the concept phase of a project have far greater performance and economic impacts than decisions made during the detailed phase, yet most engineering analysis tools have limited capabilities to carry out risk analysis, sensitivity analysis, optimization, and design space mapping.
This thesis proposes a methodology for coupling probabilistic techniques with recent advances in semi-quantitative analysis, specifically the application of interval analysis to numerical constraint satisfaction problems. The result is a method of analysis referred to as Probabilistic Constraint Satisfaction that can be used to analyze problems with probabilistic input and generate a probabilistic design space as an output. The methodology involves subdivision of the design space to a requested resolution and then testing the consistency of the constraint satisfaction problem at each subdivided location. This approach is very robust and is capable of solving a wide range of problems regardless of linearity or the availability of an explicit solution. Probabilistic data is integrated through the use of a solver which determines the valid interval for each of the probabilistic variables at a given point in the design space. The valid intervals are subsequently used to determine the probability of a feasible solution occurring at that point in the design space.
The characteristics and capabilities of this methodology are illustrated through several engineering examples and a case study that involves the conceptual design of a novel radio antenna concept. The selected case study has several features that are common to conceptual design problems for novel and complex projects including design parameters with continuous domains, trade-offs between performance targets and cost, uncertain costing data, and limited existing experience to base the design on.
27
Thornton, 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 text
28
Nightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem." Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.
Full textAbstract:
Constraint satisfaction is a very well studied and fundamental artificial intelligence technique. Various forms of knowledge can be represented with constraints, and reasoning techniques from disparate fields can be encapsulated within constraint reasoning algorithms. However, problems involving uncertainty, or which have an adversarial nature (for example, games), are difficult to express and solve in the classical constraint satisfaction problem. This thesis is concerned with an extension to the classical problem: the Quantified Constraint Satisfaction Problem (QCSP). QCSP has recently attracted interest. In QCSP, quantifiers are allowed, facilitating the expression of uncertainty. I examine whether QCSP is a useful formalism. This divides into two questions: whether QCSP can be solved efficiently; and whether realistic problems can be represented in QCSP. In attempting to answer these questions, the main contributions of this thesis are the following: - the definition of two new notions of consistency; - four new constraint propagation algorithms (with eight variants in total), along with empirical evaluations; - two novel schemes to implement the pure value rule, which is able to simplify QCSP instances; - a new optimization algorithm for QCSP; - the integration of these algorithms and techniques into a solver named Queso; - and the modelling of the Connect 4 game, and of faulty job shop scheduling, in QCSP. These are set in context by a thorough review of the QCSP literature.
29
Battle, 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 text
30
Warwick, 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 text
31
Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.
Full textAbstract:
Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.
32
Gennari, Rosella. "Mapping Inferences: Constraint Propagation and Diamond Satisfaction." Diss., Universiteit van Amsterdam, 2002. http://hdl.handle.net/10919/71553.
Full textAbstract:
The main theme shared by the two main parts of this thesis is EFFICIENT AUTOMATED REASONING.Part I is focussed on a general theory underpinning a number of efficient approximate algorithms for Constraint Satisfaction Problems (CSPs),the constraint propagation algorithms.In Chapter 3, we propose a Structured Generic Algorithm schema (SGI) for these algorithms. This iterates functions according to a certain strategy, i.e. by searching for a common fixpoint of the functions. A simple theory for SGI is developed by studying properties of functions and of the ways these influence the basic strategy. One of the primary objectives of our theorisation is thus the following: using SGI or some of its variations for DESCRIBINING and ANALISYING HOW the "pruning" and "propagation" process is carried through by constraint propagation algorithms.Hence, in Chapter 4, different domains of functions (e.g., domain orderings) are related to different classes of constraint propagation algorithms (e.g., arc consistency algorithms); thus each class of constraint propagation algorithms is associated with a "type" of function domains, and so separated from the others. Then we analys each such class: we distinguished functions on the same domains for their different ways of performing pruning (point or set based), and consequently differentiated between algorithms of the same class (e.g., AC-1 and AC-3 versus AC-4 or AC-5). Besides, we also show how properties of functions (e.g., commutativity or stationarity) are related to different strategies of propagation in constraint algorithms of the same class (see, for instance, AC-1 versus AC-3). In Chapter 5 we apply the SGI schema to the case of soft CSPs (a generalisation of CSPs with sort-of preferences), thereby clarifying some of the similarities and differences between the "classical" and soft constraint-propagation algorithms. Finally, in Chapter 6, we summarise and characterise all the functions used for constraint propagation; in fact, the other goal of our theorisation is abstracting WHICH functions, iterated as in SGI or its variations, perform the task of "pruning" or "propagation" of inconsistencies in constraint propagation algorithms.We focus on relations and relational structures in Part II of the thesis. More specifically, modal languages allow us to talk about various relational structures and their properties. Once the latter are formulated in a modal language, they can be passed to automated theorem provers and tested for satisfiability, with respect to certain modal logics. Our task, in this part, can be described as follows: determining the satisfiability of modal formulas in an efficient manner. In Chapter 8, we focus on one way of doing this: we refine the standard translation as the layered translation, and use existing theorem provers for first-order logic on the output of this refined translation. We provide ample experimental evidence on the improvements in performances that were obtained by means of the refinement.The refinement of the standard translation is based on the tree model property. This property is also used in the basic algorithm schema in Chapter 9 ---the original schema is due to~\cite{seb97}. The proposed algorithm proceeds layer by layer in the modal formula and in its candidate models, applying constraint propagation and satisfaction algorithms for finite CSPs at each layer. With Chapter 9, we wish to draw the attention of constraint programmers to modal logics, and of modal logicians to CSPs.Modal logics themselves express interesting problems in terms of relations and unary predicates, like temporal reasoning tasks. On the other hand, constraint algorithms manipulate relations in the form of constraints, and unary predicates in the form of domains or unary constraints, see Chapter 6. Thus the question of how efficiently those algorithms can be applied to modal reasoning problems seems quite natural and challenging.
33
Budzynski, Louise. "Algorithmic barriers in random constraint satisfaction problems." Thesis, Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLE013.
Full textAbstract:
La complexité typique des Problèmes de Satisfaction de Contraintes (CSP) peut être étudiée à l'aide d'ensembles aléatoires de contraintes. On observe un phénomène de seuil quand la densité de contraintes augmente. En particulier à la transition de clustering, l'ensemble des solutions typiques se fracture en groupes de solutions séparés les uns des autres. Dans cette thèse nous introduisons un biais qui brise l'uniformité entre les solutions d'une instance de CSP, et nous étudions son effet sur la valeur du seuil de clustering. Nous étudions en particulier le problème de bicoloriage de k-hypergraphes. Pour de petites valeurs de k, nous montrons que ce biais peut augmenter la valeur du seuil clustering, et que cela a un effet positif sur les performances de l'algorithme de Simulated Annealing pour la recherche de solutions d'une instance du problème de bicoloriage. Dans la limite où k tend vers l'infini, nous calculons le développement asymptotique du seuil de clustering pour la mesure uniforme et pour une mesure biaisée. Nous évaluons le gain obtenu avec cette implémentation du biaisThe 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
34
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 textAbstract:
Standard Planning Domain Definition Language (PDDL) planning problem definitions may be reformulated and solved using alternative techniques. One such paradigm, Constraint Programming (CP), has successfully been used in various planner architectures in recent years. The efficacy of a given constraint reformulation depends on the encoding method, search technique(s) employed, and the consequent amount of propagation. Despite advances in this area, constraint based planners have failed to match the performance of other approaches. One reason for this is that the structural information that is implicit in the domain/problem instance description is lost in the reformulation process. Hence, to achieve better performance, a constraint based planner should have an appropriate encoding and a search procedure informed by the structure of the original problem. This thesis describes a system that aims to improve planner performance by employing such methods. The planner uses a table-constraint encoding together with a new variable/ value ordering heuristic. This ordered, goal oriented guidance reduces the search space and better directs the search focus. The system also makes use of novel meta variable techniques for goal locking and resource assignment. These improve propagation and prune the search space. This CP based planning architecture is shown to perform well on a range of problem instances taken from recent International Planning Competitions (IPCs).
35
Grant, Stuart Alexander. "Phase transition behaviour in constraint satisfaction problems." Thesis, University of Leeds, 1997. http://etheses.whiterose.ac.uk/1273/.
Full textAbstract:
Many problems in artificial intelligence and computer science can be formulated as constraint satisfaction problems (CSPs). A CSP consists of a set of variables among which a set of constraints are imposed, with a solution corresponding to an assignment for every variable such that no constraints are violated. Most forms of CSP are NP-complete. Recent research has shown that the CSP exhibits a phase transition as a control parameter is varied. This transition lies between a region where most problems are easy and soluble, and a region where most problems are easy but insoluble. In the intervening phase transition region, the average problem difficulty is greatest. Phase transition behaviour can be exploited to create test beds of hard and easy problems for CSP algorithms. In this thesis, we study the phase transition of the binary CSP and examine various aspects of complete search algorithms for it. The phenomenon of exceptionally hard problems (`ehps') is examined in detail: these are rare searches on easy problems which become exceptionally expensive for a particular complete algorithm following a poor early search move. An explanation for the occurrence of ehps is proposed, and the relative susceptibility of certain algorithms to the phenomenon is explored. We then show that the phase transition paradigm can be applied to two tasks of polynomial cost complexity: attempting to establish arc and path consistency in a CSP. Phase transition behaviour analogous to that found when searching for a solution is demonstrated for these tasks, and the effectiveness and cost of establishing arc and path consistency is examined. The theme of establishing consistency in CSPs is extended by studying an algorithm which maintains arc consistency during search. Its performance is compared with that of an algorithm which maintains a lower level of consistency, and it is shown that the higher level of consistency reduces average search cost and ehp behaviour on many types of CSP. Finally, the subject of dynamically selecting the variable to instantiate at each stage in the search process is considered. We compare a number of heuristics which attempt to select the variable most likely to lead to failure, and show that the supposed principle behind these appears to be fundamentally flawed.
36
Curtis, Suniel David. "Constraint satisfaction approaches to bus driver scheduling." Thesis, University of Leeds, 2000. http://etheses.whiterose.ac.uk/1287/.
Full textAbstract:
The bus driver scheduling problem consists of assigning bus work to drivers so that all the bus work is covered and a combination of the number of drivers and associated costs is minimised. Restrictions imposed by logistic, legal and union agreements complicate the problem. Successful present day systems for computerised driver scheduling often use mathematical programming combined with heuristics. Purely heuristic approaches have found it very difficult to produce efficient driver schedules for large scheduling problems. Furthermore, some of these approaches may not be easily adaptable to different conditions. This thesis presents two new ways of using constraint satisfaction to form driver schedules. The two methods differ in their approach, one being a systematic constraint programming approach and the other being an adaptation of a local search method called GENET. The constraint programming approach uses a similar approach to mathematical programming systems in selecting the schedule from a large number of possible shifts, to allow adaptation to different regulations. In particular, a set partitioning formulation is used. It then makes use of the structure of the problem and the relaxed linear programming solution to the problem in producing a schedule. The GENET system has been adapted to cope with minimising the numbers of drivers in a schedule and with the memory problems caused by the huge number of constraints involved in the set partitioning model. The constraint programming approach has been shown to solve successfully several small scheduling problems from different companies using varying regulations. Local search procedures have hitherto not had great success on driver scheduling problems. GENET has been adapted to solve some of the small schedules from its initial state where it could not solve any. Features of the adaptation may be of interest to researchers using GENET on similar problems.
37
Nguyen, Thi Hong Hiep. "Strong consistencies for weighted constraint satisfaction problems." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30004/document.
Full textAbstract:
Cette thèse se focalise sur l'étude de cohérences locales fortes afin de résoudre des problèmes d'optimisation sur des réseaux de fonctions de coûts (ou réseaux de contraintes pondérées). Ces méthodes fournissent le minorant nécessaire pour des approches de type "Séparation-Evaluation". Nous étudions dans un premier temps la cohérence d'Arc virtuelle (VAC), une des plus fortes cohérences d'arcs du domaine, qui est établie via l'établissement de la cohérence d'arc dure dans une séquence de réseaux de contraintes classiques. L'algorithme itératif pour établir VAC est amélioré via l'introduction d'une incrémentalité accrue, exploitant la cohérence d'arc dynamique. La nouvelle méthode est aussi capable de maintenir VAC efficacement pendant la recherche lorsque les réseaux de contraintes pondérées sont dynamiquement modifiés par les opérations de branchement. Dans une seconde partie, nous nous intéressons à des cohérences de domaines plus fortes, inspirées de cohérences similaires dans les réseaux de contraintes classiques (cohérence de chemin inverse, réduite ou Max-réduite). Pour chaque cohérence dure, plusieurs cohérences souples ont été proposées pour les réseaux de contraintes pondérées. Les nouvelles cohérences fournissent un minorant plus fort que celui des cohérences d'arc souples en traitant les triplets de variables connectées deux à deux par des fonctions de coûts binaires. Dans cette thèse, nous étudions les propriétés des nouvelles cohérences, les implémentons et les testons sur une variété de problèmesThis 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
38
Cameron, Heather M. "Constraint satisfaction for interactive 3-D model acquisition." Thesis, University of British Columbia, 1990. http://hdl.handle.net/2429/28937.
Full textAbstract:
More and more computer applications are using three-dimensional models for a variety of uses (e.g. CAD, graphics, recognition). A major bottleneck is the acquisition of these models. The easiest method for designing the models is to build them directly from images of the object being modelled. This paper describes the design of a system, MOLASYS (for MOdeL Acquisition SYStem), that allows the user to build object models interactively from underlying images. This would not only be easier for the user, but also more accurate as the models will be built directly satisfying the dimensions, shape, and other constraints present in the images.
The object models are constructed by constraining model points and edges to match points in the image objects. The constraints are defined by the user and expressed using a Jacobian matrix of partial derivatives of the errors with respect to a set of camera and model parameters. MOLASYS then uses Newton's method to solve for corrections to the parameters that will reduce the errors specified in the constraints to zero. Thus the user describes how the system will change, and the program determines the best way to accomplish the desired changes.
The above techniques, implemented in MOLASYS, have resulted in an intuitive and flexible tool for the interactive creation of three-dimensional models.Science, Faculty of
Computer Science, Department of
Graduate
39
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 text
40
Hast, 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 text
41
Zhang, 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 text
42
Egri, 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 textAbstract:
Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1,x2,...,xn and a list of constraints of the form "(x7,x2,...,x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. In recent years, combined logical and algebraic approaches to understand the complexity of CSPs within the complexity class P have been especially fruitful. In particular, precise algebraic conditions on Γ have been conjectured to be sufficient and necessary for the membership of CSP(Γ) in the complexity classes L and NL (under standard complexity theoretic assumptions, e.g. L different from NL). These algebraic conditions are known to be necessary, and from the algorithmic side, a promising body of evidence is fast-growing. The main tools to establish membership of CSPs in L and NL are the logic programming fragments symmetric and linear Datalog, respectively. This thesis is centered around the above algebraic conjecture for CSPs in L, and most of the technical work is devoted to establishing the membership of several large classes of CSPs in L. Among other results, we characterize all graphs for which the list homomorphism problem is in L, a well-studied and natural class of CSPs. We also extend this result to obtain a complete characterization of the complexity of the list homomorphism for graphs. We develop new tool (dualities for symmetric Datalog) to show membership of CSPs in L, prove an L − NL dichotomy for the list homomorphism problem for oriented paths, provide results about the structure and polymorphisms of Maltsev digraphs, and also contribute to the conjecture of Dalmau that every CSP in NL is in fact in linear Datalog.Les 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".
43
Grayland, Andrews. "Automated static symmetry breaking in constraint satisfaction problems." Thesis, University of St Andrews, 2011. http://hdl.handle.net/10023/1718.
Full textAbstract:
Variable symmetries in constraint satisfaction problems can be broken by adding lexicographic ordering constraints. Existing general methods of generating such sets of ordering constraints can produce a huge number of additional constraints. This adds an unacceptable overhead to the solving process. Methods exist by which this large set of constraints can be reduced to a much smaller set automatically, but their application is also prohibitively costly. In contrast, this thesis takes a bottom up approach to generating symmetry breaking constraints. This will involve examining some commonly-occurring families of mathematical groups and deriving a general formula to produce a minimal set of ordering constraints which are sufficient to break all of the symmetry that each group describes. In some cases it is known that there exists no manageable sized sets of constraints to break all symmetries. One example of this occurs with matrix row and column symmetries. In such cases, incomplete symmetry breaking has been used to great effect. Double lex is a commonly used incomplete symmetry breaking technique for row and column symmetries. This thesis also describes another similar method which compares favourably to double lex. The general formulae investigated are used as building blocks to generate small sets of ordering constraints for more complex groups, constructed by combining smaller groups. Through the utilisation of graph automorphism tools and the groups and permutations software GAP we provide a method of defining variable symmetries in a problem as a group. Where this group can be described as the product of smaller groups, with known general formulae, we can construct a minimal set of ordering constraints for that problem automatically. In summary, this thesis provides the theoretical background necessary to apply efficient static symmetry breaking to constraint satisfaction problems. It also goes further, describing how this process can be automated to remove the necessity of having an expert CP practitioner, thus opening the field to a larger number of potential users.
44
Akatov, 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 textAbstract:
Constraint Satisfaction Problems (CSPs) are NP-complete in general, however, there are many tractable subclasses that rely on the restriction of the structure of their underlying hypergraphs. It is a well-known fact, for instance, that CSPs whose underlying hypergraph is acyclic are tractable. Trying to define “nearly acyclic” hypergraphs led to the definition of various hypergraph decomposition methods. An important member in this class is the hypertree decomposition method, introduced by Gottlob et al. It possesses the property that CSPs falling into this class can be solved efficiently, and that hypergraphs in this class can be recognized efficiently as well. Apart from polynomial tractability, complexity analysis has shown, that both afore-mentioned problems lie in the low complexity class LOGCFL and are thus moreover efficiently parallelizable. A parallel algorithm has been proposed for the “evaluation problem”, however all algorithms for the “recognition problem” presented to date are sequential. The main contribution of this dissertation is the creation of an object oriented programming library including a task scheduler which allows the parallelization of a whole range of computational problems, fulfilling certain complexity-theoretic restrictions. This library merely requires the programmer to provide the implementation of several classes and methods, representing a general alternating algorithm, while the mechanics of the task scheduler remain hidden. In particular, we use this library to create an efficient parallel algorithm, which computes hypertree decompositions of a fixed width. Another result of a more theoretical nature is the definition of a new type of decomposition method, called Balanced Decompositions. Solving CSPs of bounded balanced width and recognizing such hypergraphs is only quasi-polynomial, however still parallelizable to a certain extent. A complexity-theoretic analysis leads to the definition of a new complexity class hierarchy, called the DC-hierarchy, with the first class in this hierarchy, DC1 , precisely capturing the complexity of solving CSPs of bounded balanced width.
45
Houghton, 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 textAbstract:
Constraint Satisfaction is used in the solution of a wide variety of important problems such as frequency assignment, code analysis, and scheduling. It is apparent that the modelling process is key to the success of any constraint based technique, and much work has been done on the identification of good models [FJHM05]. One of the key choices made during the modelling process is the selection of a constraint representation with which to express the constraints [HS02]. Whilst practitioners will commonly use an implicit representation, most existing structural tractability results are defined for explicit representation. We address a well-known anomaly in structural tractability theory, that acyclic instances are tractable when expressed explicitly, but may not be when expressed implicitly, and show that there is a link between representation and tractability, We introduce the notion of interaction width in order to address this disconnect between theory and practice, and use this to define new tractable classes by applying existing structural tractability results to different constraint representations, We show that for a given succinct representation, a non-trivial class of instances with bounded interaction width can be transformed into an explicit representation in polynomial time 50 that existing structural tractability results may be applied, We compare our work to existing results Cor alternative succinct representutions and show that the tractable classes we have defined arc incomparable and novel, and can be used to deduce new tractable classes for SAT. 3
46
Wu, Yi. "The Approximability of Learning and Constraint Satisfaction Problems." Research Showcase @ CMU, 2010. http://repository.cmu.edu/dissertations/24.
Full textAbstract:
An α-approximation algorithm is an algorithm guaranteed to output a solutionthat is within an α ratio of the optimal solution. We are interested in thefollowing question: Given an NP-hard optimization problem, what is the bestapproximation guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of NP-hardproblems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems.
For CSPs, we mainly study the approximability of MAX CUT, MAX 3-CSP,MAX 2-LINR, VERTEX-PRICING, as well as serval variants of the UNIQUEGAMES.• The problem of MAX CUT is to find a partition of a graph so as to maximizethe number of edges between the two partitions. Assuming theUnique Games Conjecture, we give a complete characterization of the approximationcurve of the MAX CUT problem: for every optimum value ofthe instance, we show that certain SDP algorithm with RPR2 roundingalways achieve the optimal approximation curve.• The input to a 3-CSP is a set of Boolean constraints such that each constraintcontains at most 3 Boolean variables. The goal is to find an assignmentto these variables to maximize the number of satisfied constraints.We are interested in the case when a 3-CSP is satisfiable, i.e.,there does exist an assignment that satisfies every constraint. Assumingthe d-to-1 conjecture (a variant of the Unique Games Conjecture), weprove that it is NP-hard to give a better than 5/8-approximation for theproblem. Such a result matches a SDP algorithm by Zwick which givesa 5/8-approximation problem for satisfiable 3-CSP. In addition, our resultalso conditionally resolves a fundamental open problem in PCP theory onthe optimal soundness for a 3-query nonadaptive PCP system for NP withperfect completeness.• The problem of MAX 2-LINZ involves a linear systems of integer equations;these equations are so simple such that each equation contains atmost 2 variables. The goal is to find an assignment to the variables so asto maximize the total number of satisfied equations. It is a natural generalizationof the Unique Games Conjecture which address the hardness ofthe same equation systems over finite fields. We show that assuming theUnique Games Conjecture, for a MAX 2-LINZ instance, even that thereexists a solution that satisfies 1−ε of the equations, it is NP-hard to findone that satisfies ² of the equations for any ε > 0.
47
Kerrigan, 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 text
48
Kim, 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 textAbstract:
While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c^k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n^k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.
49
Li, 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 text
50
Liu, Bing. "Reinforcement planning for resource allocation and constraint satisfaction." Thesis, University of Edinburgh, 1988. http://hdl.handle.net/1842/19055.
Full text