Relevant bibliographies by topics / Constraints satisfaction problem / Dissertations / Theses
To see the other types of publications on this topic, follow the link: Constraints satisfaction problem.

Dissertations / Theses on the topic 'Constraints satisfaction problem'

Author: Grafiati
Published: 4 June 2021
Last updated: 8 June 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 dissertations / theses for your research on the topic 'Constraints satisfaction problem.'

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

Nightingale, Peter. "Consistency and the quantified constraint satisfaction problem /." St Andrews, 2007. http://hdl.handle.net/10023/759.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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
APA, Harvard, Vancouver, ISO, and other styles
3

Malibary, Areej. "Addressing Supply Chain Management as a Distributed Multi-Layered Constraints Satisfaction Problem." Thesis, University of Essex, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.520096.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Karakoc, Erman. "Web Service Composition Under Resource Allocation Constraints." Master's thesis, METU, 2007. http://etd.lib.metu.edu.tr/upload/12608309/index.pdf.

Full text
Abstract:
Web service composition is an inevitable aspect of web services technology, which solves complex problems by combining available basic services and ordering them to best suit the problem requirements. Automatic composition gives us flexibility of selecting best candidate services at composition time, this would require the user to define the resource allocation constraints for selecting and composing candidate web services. Resource allocation constraints define restrictions on how to allocate resources, and scheduling under resource allocation constraints to provide proper resource allocation
APA, Harvard, Vancouver, ISO, and other styles
5

Sadeg, Lamia. "Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0314.

Full text
Abstract:
Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, un
APA, Harvard, Vancouver, ISO, and other styles
6

Sadeg, Lamia. "Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes." Electronic Thesis or Diss., Université de Lorraine, 2016. http://www.theses.fr/2016LORR0314.

Full text
Abstract:
Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, un
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 const
APA, Harvard, Vancouver, ISO, and other styles
8

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
APA, Harvard, Vancouver, ISO, and other styles
9

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 text
Abstract:
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 cons
APA, Harvard, Vancouver, ISO, and other styles
10

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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
11

Tran-Dang, Hoa. "3D Spatial Modeling of Stacked Containers based on Wireless Sensor Network : application to the physical internet." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0049/document.

Full text
Abstract:
Le paradigme de l’Internet Physique a été introduit il y a quelques années pour transformer globalement la manière dont les objets physiques seront manipulés, entreposés et transportés dans le cadre d’une logistique durable. L’une des caractéristiques importante de l’Internet Physique est liée à l’encapsulation des marchandises dans des conteneurs modulaires standardisés. Le modèle de fonctionnement proposé de l’Internet Physique, s’il rationnalise les transports, engendre des manutentions plus nombreuses, en particulier au sein des PI-hubs, où les opérations de routage, de déchargement et (re
APA, Harvard, Vancouver, ISO, and other styles
12

Gharbi, Nebras. "On compressing and parallelizing constraint satisfaction problems." Thesis, Artois, 2015. http://www.theses.fr/2015ARTO0406/document.

Full text
Abstract:
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 ce
APA, Harvard, Vancouver, ISO, and other styles
13

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
APA, Harvard, Vancouver, ISO, and other styles
14

Bain, Stuart, and n/a. "Evolving Algorithms for Over-Constrained and Satisfaction Problems." Griffith University. School of Information and Communication Technology, 2007. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20071126.080227.

Full text
Abstract:
The notion that a universally effective problem solver may still exist, and is simply waiting to be found, is slowly being abandoned in the light of a growing body of work reporting on the narrow applicability of individual heuristics. As the formalism of the constraint satisfaction problem remains a popular choice for the representation of problems to be solved algorithmically, there exists an ongoing need for new algorithms to effciently handle the disparate range of problems that have been posed in this representation. Given the costs associated with manually applying human algorithm develo
APA, Harvard, Vancouver, ISO, and other styles
15

Bain, Stuart. "Evolving Algorithms for Over-Constrained and Satisfaction Problems." Thesis, Griffith University, 2007. http://hdl.handle.net/10072/365848.

Full text
Abstract:
The notion that a universally effective problem solver may still exist, and is simply waiting to be found, is slowly being abandoned in the light of a growing body of work reporting on the narrow applicability of individual heuristics. As the formalism of the constraint satisfaction problem remains a popular choice for the representation of problems to be solved algorithmically, there exists an ongoing need for new algorithms to effciently handle the disparate range of problems that have been posed in this representation. Given the costs associated with manually applying human algorithm develo
APA, Harvard, Vancouver, ISO, and other styles
16

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
APA, Harvard, Vancouver, ISO, and other styles
17

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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
18

Nightingale, Peter William. "Consistency and the Quantified Constraint Satisfaction Problem". Thesis, University of St Andrews, 2007. http://hdl.handle.net/10023/759.

Full text
Abstract:
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 attra
APA, Harvard, Vancouver, ISO, and other styles
19

Madelaine, Florent. "Constraint satisfaction problems and related logic." Thesis, University of Leicester, 2003. http://hdl.handle.net/2381/30524.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
20

Escamocher, Guillaume. "Forbidden patterns in constraint satisfaction problems." Toulouse 3, 2014. http://thesesups.ups-tlse.fr/2283/.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
21

Black, Daniel Peter. "Search in weighted constraint satisfaction problems." Thesis, University of Leeds, 2003. http://etheses.whiterose.ac.uk/1309/.

Full text
Abstract:
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 probl
APA, Harvard, Vancouver, ISO, and other styles
22

Carbonnel, Clément. "Harnessing tractability in constraint satisfaction problems." Thesis, Toulouse, INPT, 2016. http://www.theses.fr/2016INPT0118/document.

Full text
Abstract:
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 t
APA, Harvard, Vancouver, ISO, and other styles
23

Tran-Dang, Hoa. "3D Spatial Modeling of Stacked Containers based on Wireless Sensor Network : application to the physical internet." Electronic Thesis or Diss., Université de Lorraine, 2017. http://www.theses.fr/2017LORR0049.

Full text
Abstract:
Le paradigme de l’Internet Physique a été introduit il y a quelques années pour transformer globalement la manière dont les objets physiques seront manipulés, entreposés et transportés dans le cadre d’une logistique durable. L’une des caractéristiques importante de l’Internet Physique est liée à l’encapsulation des marchandises dans des conteneurs modulaires standardisés. Le modèle de fonctionnement proposé de l’Internet Physique, s’il rationnalise les transports, engendre des manutentions plus nombreuses, en particulier au sein des PI-hubs, où les opérations de routage, de déchargement et (re
APA, Harvard, Vancouver, ISO, and other styles
24

Powell, Robert David. "Complexity classifications for the valued constraint satisfaction problem." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11485/.

Full text
Abstract:
In a valued constraint satisfaction problem (VCSP), the goal is to find an assignment of values to variables that minimizes a given sum of functions. Each function in the sum depends on a subset of variables, takes values which are rational numbers or infinity, and is chosen from a fixed finite set of functions called a constraint language. We study how the computational complexity of this problem depends on the constraint language. We often consider the case where infinite values are disallowed, and refer to such constraint languages as being finite-valued. If we consider such finite-valued c
APA, Harvard, Vancouver, ISO, and other styles
25

Wang, Pengming. "Descriptive complexity of constraint problems." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/276188.

Full text
Abstract:
Constraint problems are a powerful framework in which many common combinatorial problems can be expressed. Examples include graph colouring problems, Boolean satisfaction, graph cut problems, systems of equations, and many more. One typically distinguishes between constraint satisfaction problems (CSPs), which model strictly decision problems, and so-called valued constraint satisfaction problems (VCSPs), which also include optimisation problems. A key open problem in this field is the long-standing dichotomy conjecture by Feder and Vardi. It claims that CSPs only fall into two categories: Tho
APA, Harvard, Vancouver, ISO, and other styles
26

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
APA, Harvard, Vancouver, ISO, and other styles
27

Budzynski, Louise. "Algorithmic barriers in random constraint satisfaction problems." Thesis, Université Paris sciences et lettres, 2020. http://www.theses.fr/2020UPSLE013.

Full text
Abstract:
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-hyperg
APA, Harvard, Vancouver, ISO, and other styles
28

Grant, Stuart Alexander. "Phase transition behaviour in constraint satisfaction problems." Thesis, University of Leeds, 1997. http://etheses.whiterose.ac.uk/1273/.

Full text
Abstract:
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 interven
APA, Harvard, Vancouver, ISO, and other styles
29

Nguyen, Thi Hong Hiep. "Strong consistencies for weighted constraint satisfaction problems." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30004/document.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
30

Andersson, Jakob. "Automatic Invoice Data Extraction as a Constraint Satisfaction Problem." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-411596.

Full text
Abstract:
Invoice processing has traditionally been heavily dependent onmanual labor, where the task is to identify and move certaininformation from an origin to a destination. A time demandingtask with a high interest of automation to reduce time ofexecution, fault-risk and cost.With the evergrowing interest in automation and ArtificialIntelligence (AI), this thesis will explore the possibilities ofautomating the task of extracting and mapping information ofinterest by defining the problem as a Constraint OptimizationProblem (COP) using numeric relations between present information.The problem is then
APA, Harvard, Vancouver, ISO, and other styles
31

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
APA, Harvard, Vancouver, ISO, and other styles
32

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 text
Abstract:
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 constraint
APA, Harvard, Vancouver, ISO, and other styles
33

Grayland, Andrews. "Automated static symmetry breaking in constraint satisfaction problems." Thesis, University of St Andrews, 2011. http://hdl.handle.net/10023/1718.

Full text
Abstract:
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-occ
APA, Harvard, Vancouver, ISO, and other styles
34

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 text
Abstract:
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 f
APA, Harvard, Vancouver, ISO, and other styles
35

Wu, Yi. "The Approximability of Learning and Constraint Satisfaction Problems." Research Showcase @ CMU, 2010. http://repository.cmu.edu/dissertations/24.

Full text
Abstract:
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 UNIQUEGAME
APA, Harvard, Vancouver, ISO, and other styles
36

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 text
Abstract:
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 ty
APA, Harvard, Vancouver, ISO, and other styles
37

Climent, Aunés Laura Isabel. "Robustness and stability in dynamic constraint satisfaction problems." Doctoral thesis, Universitat Politècnica de València, 2014. http://hdl.handle.net/10251/34785.

Full text
Abstract:
Constraint programming is a paradigm wherein relations between variables are stated in the form of constraints. It is well-known that many real life problems can be modeled as Constraint Satisfaction Problems (CSPs). Much effort has been spent to increase the efficiency of algorithms for solving CSPs. However, many of these techniques assume that the set of variables, domains and constraints involved in the CSP are known and fixed when the problem is modeled. This is a strong limitation because many problems come from uncertain and dynamic environments, where both the original problem may evo
APA, Harvard, Vancouver, ISO, and other styles
38

Likeman, Martin. "A study of centralised and distributed problem solving applied to water supply scheduling." Thesis, University of Reading, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.241628.

Full text
APA, Harvard, Vancouver, ISO, and other styles
39

Uppman, Hannes. "On Some Combinatorial Optimization Problems : Algorithms and Complexity." Doctoral thesis, Linköpings universitet, Programvara och system, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-116859.

Full text
Abstract:
This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems. A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). In this problem we are given a set of variables and a collection of constraints, each of which is constraining some variables with a relation in the language. The goal is to determine if domain values can be assigned to the variables in a way that satisfies all constraints. An import
APA, Harvard, Vancouver, ISO, and other styles
40

Magaji, Amina Sambo-Muhammad. "Combining search strategies for distributed constraint satisfaction." Thesis, Robert Gordon University, 2015. http://hdl.handle.net/10059/1374.

Full text
Abstract:
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 const
APA, Harvard, Vancouver, ISO, and other styles
41

Paris, Nicolas. "Intégration de techniques CSP pour la résolution du problème WCSP." Thesis, Artois, 2014. http://www.theses.fr/2014ARTO0405/document.

Full text
Abstract:
Cette thèse se situe dans le contexte de la programmation par contraintes (CP). Plus précisément, nous nous sommes intéressés au problème de satisfaction de contraintes pondérées (WCSP). De nombreuses approches ont été proposées pour traiter ce problème d’optimisation. Les méthodes les plus efficaces utilisent des cohérences locales souples sophistiquées comme par exemple la cohérence d’arc directionnelle complète FDAC∗, la cohérence d’arc directionnelle existentielle EDAC∗, etc. Établies grâce à des opérations de transferts de coût préservant l’équivalence des réseaux, l’utilisation de ces co
APA, Harvard, Vancouver, ISO, and other styles
42

Lagerkvist, Victor. "Restricted Constraint Satisfaction Problems and the Exponential-time Hypothesis." Thesis, Linköpings universitet, Institutionen för datavetenskap, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-82343.

Full text
Abstract:
A constraint satisfaction problem (CSP) can be represented as two structures: the structure induced by the variables and the structure induced by the constraint language. Both these parameters are amenable to restrictions which affects the complexity of the resulting problems. In this thesis we shall use both constraint language restrictions and structural restrictions in order to create problems that can be solved as efficiently as possible. The language restrictions are based on creating a language that in terms of frozen partial clone theory has the largest number of polymorphic functions.
APA, Harvard, Vancouver, ISO, and other styles
43

Green, Martin James. "New methods for the tractability of constraint satisfaction problems." Thesis, Royal Holloway, University of London, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.417366.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

Wahbi, Mohamed. "Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00718537.

Full text
Abstract:
Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plus
APA, Harvard, Vancouver, ISO, and other styles
45

Faben, John. "The complexity of modular counting in constraint satisfaction problems." Thesis, Queen Mary, University of London, 2012. http://qmro.qmul.ac.uk/xmlui/handle/123456789/8488.

Full text
Abstract:
Constraint Satisfaction Problems are a broad class of combinatorial problems, including several classical decision problems such as graph colouring and SAT, and a range of problems' from other areas, including statistical physics, DNA sequencing and scheduling problems. There are a variety of dichotomy theorems for various subclasses of CSP in various complexity classes, one of the most noteable is Bulatov's proof that a dichotomy holds for #CSP [Bu108], that is, all #CSP problems are either #P-complete or in FP. In this thesis, we look at the complexity of modular counting in some restricted
APA, Harvard, Vancouver, ISO, and other styles
46

Winter, Mark J. "Knowledge refinement in constraint satisfaction and case classification problems." Thesis, University of Aberdeen, 1999. http://digitool.abdn.ac.uk/R?func=search-advanced-go&find_code1=WSN&request1=AAIU106810.

Full text
Abstract:
Knowledge-Base Refinement (KBR) systems are an attempt to help with the difficulties of detecting and correcting errors in a knowledge-base. This thesis investigates Knowledge-Base Refinement within the two problem solving paradigms of Case-Based Reasoning and Constraint Based Reasoning. Case-Based Reasoners make use of cases which represent previous problem solving incidents. Constraint Satisfaction Problems are represented by a set of variables, the possible values these variables can take and a set of constraints further restricting their possible values. This thesis argues that if the prob
APA, Harvard, Vancouver, ISO, and other styles
47

Nguyen, Van-Hau. "SAT Encodings of Finite CSPs." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-162186.

Full text
Abstract:
Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a theoretical interest. Nowadays, the picture is very different. SAT solving becomes mature and is a successful approach for tackling a large number of applications, ranging from artificial intelligence to industrial hardware design and verification. SAT solving consists of encodings and solvers. In
APA, Harvard, Vancouver, ISO, and other styles
48

Jones, Charles H. "A Mathematical Model for Instrumentation Configuration." International Foundation for Telemetering, 2010. http://hdl.handle.net/10150/604273.

Full text
Abstract:
ITC/USA 2010 Conference Proceedings / The Forty-Sixth Annual International Telemetering Conference and Technical Exhibition / October 25-28, 2010 / Town and Country Resort & Convention Center, San Diego, California<br>This paper describes a model of how to configure settings on instrumentation. For any given instrument there may be 100s of settings that can be set to various values. However, randomly selecting values for each setting is not likely to produce a valid configuration. By "valid" we mean a set of setting values that can be implemented by each instrument. The valid configurations mu
APA, Harvard, Vancouver, ISO, and other styles
49

Kwan, Alvin Chi Ming. "A framework for mapping constraint satisfaction problems to solution methods." Thesis, University of Essex, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.339436.

Full text
APA, Harvard, Vancouver, ISO, and other styles
50

Lynden, John M. "Diversification and Intensification in Hybrid Metaheuristics for Constraint Satisfaction Problems." Diss., NSUWorks, 2019. https://nsuworks.nova.edu/gscis_etd/1076.

Full text
Abstract:
Metaheuristics are used to find feasible solutions to hard Combinatorial Optimization Problems (COPs). Constraint Satisfaction Problems (CSPs) may be formulated as COPs, where the objective is to reduce the number of violated constraints to zero. The popular puzzle Sudoku is an NP-complete problem that has been used to study the effectiveness of metaheuristics in solving CSPs. Applying the Simulated Annealing (SA) metaheuristic to Sudoku has been shown to be a successful method to solve CSPs. However, the ‘easy-hard-easy’ phase-transition behavior frequently attributed to a certain class of CS
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Constraints satisfaction problem' for other source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography