Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"Arc consistency"”.
-
Empirical evaluation of Soft Arc Consistency algorithms for solving Constraint Optimization Problems
… approaches have been widely studied, including search, propagation, and heuristics. There are still challenging real-world COPs that cannot be solved using current methods. We implemented and compared several consistency propagation algorithms, which include W-AC*2001, EDAC, VAC, and xAC. …
-
BINARY ENCODINGS FOR SOLVING AD-HOC CONSTRAINTS
… binary CSPs and propagators proposed to enforce Arc Consistency (AC) on binary constraints. Additionally, several well-known binary encoding methods can be used to transform non-binary constraints into binary constraints. However, in more recent times (from the 1990s), research has focused on …
-
Consistency techniques in constraint networks
Consistency techniques play an important role in studying constraint networks. We focus on two aspects of them: consistency as a pruning tool and consistency as a tool to relate local consistency and global consistency. For the first aspect, we mainly study arc consistency (AC). We find a simple …
-
Some Enhancement Methods For Backtracking-Search In Solving Multiple Permutation Problems
… some enhancement methods for backtracking-search in solving multiple permutation problems. Some well-known NP-complete multiple permutation problems are Quasigroup Completion Problem and Sudoku. Multiple permutation problems have been getting a lot of attention in the literature in the recent …
-
Using discrimination graphs to represent visual knowledge
… addressed. Generally, specialization hierarchies are used to suppress a potential explosion in local interpretations. Such a solution has problems, as many local interpretations cannot be represented by a single hierarchy. As well, ambiguous and hypothetical interpretations tend to be …
-
A constraint-based framework for configuration
The research presented here aims at providing a comprehensive framework for solving configuration problems, based on the Constraint Satisfaction paradigm. This thesis is addressing the two main issues raised by a configuration task: modeling the problem and solving it efficiently. Our approach …
-
Higher-Level Consistencies: Where, When, and How Much
… CSPs are solved by inference (i.e., enforcing consistency), conditioning (i.e., doing search), or, more commonly, by interleaving the two mechanisms. The most common consistency property enforced during search is Generalized Arc Consistency (GAC). In recent years, new algorithms that enforce …
-
ΔΙΑΤΑΞΕΙΣ ΔΙΑΓΡΑΦΩΝ, ΠΑΙΧΝΙΔΙΑ ΚΑΙ ΕΛΑΣΣΟΝΑ ΣΕ ΓΡΑΦΗΜΑΤΑ
… TO THEIR VALUES, THEIR RELATION WITH GRAPH SEARCHING PROBLEMS AND THEIR APPLICATION ON THE CONSTRAINT SATISFACTION PROBLEM AND THE ROUTING PROBLEM ON DISTRIBUTED COMPUTING SYSTEMS. THE BASIC RESULTS ARE THE FOLLOWING. 1) SUBLINEAR ALGORITHM FOR ENFORCING PARTIAL ARE CONSISTENCY ON NETWORKS OF …
-
New Relational Consistency Algorithms and a Flexible Solver Architecture for Integrating Them during Search
Consistency algorithms, which perform inference, are at the heart of Constraint Programming. The strongest consistency level provided in most constraint solvers is Generalized Arc Consistency (GAC). In recent years, higher-level consistencies, especially relational consistencies, were shown to be …
-
Constraint programming: algorithms and systems
… problems, Constraint Programming is based on search methods and constraint propagation. This dissertation contributes on both. Specifically: (i) We develop novel search methods that are based on new heuristics. These new heuristics implement the gradual randomization of deterministic heuristics. …
-
Domain value mutation and other techniques for constraint satisfaction problems
… usually requires chronological backtracking search that interleaves variable assignments with various kinds of inferences in order to reduce the search space. This dissertation comprises two parts. The first part deals with a modification of the classical CSP model that allows a value to be …
-
Adaptive strategies for solving contraint satisfaction problems
… CSPs have attracted the interest of many researchers. General speaking a strategy that uses the results of its own search experience to modify its subsequent behavior does adaptive search In this dissertation we explore adaptive strategies for backtracking search on various levels. First, we …
-
APPLICATION OF FUZZY LOGIC TO PARTIAL CONSTRAINT SATISFACTION PROBLEM
Constraint-directed search techniques are an efficient approc1ch for solving constraint satisfaction problems (CSPs). These techniques usually use constraint propagation to simplify the original problem, and then employ intelligent backtracking to search for a solution, or all possible solutions, …
-
Integrating Probabilistic Reasoning with Constraint Satisfaction
… the two areas. For instance, we characterize search and inference in constraint reasoning as summation and multiplication (or disjunction and conjunction) in the probabilistic space; necessary but insufficient consistency conditions for solutions to constraint problems (like arc-consistency) …
-
Optimal Planning with Learned Neural Network Transition Models
… in the literature that maintains generalized arc-consistency property through unit propagation -- an important property that facilitates efficiency in WP-MaxSAT solvers. For all compilations presented, we experimentally demonstrate their performance over multiple learned planning domains and …
-
Composing classical and quantum relaxations of CSP and structure isomorphism
… monads, such as the basic linear programming and arc-consistency monads. On the positive side, we identify sufficient conditions under which a distributive law between game comonads and distribution minion monads exists. Neither our no-go theorems nor our positive results apply to the quantum …
-
Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems
… tackle this inherent problem. Enforcing a local consistencyproperty is one of the most important such techniques.Bounds Consistency (BC) and Generalised Arc Consistency (GAC) are the two mostwidely studied and used local consistencies in CP solvers. While there exist strongerlocal consistency …
-
Phase transition behaviour in constraint satisfaction problems
… 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 …
-
Pseudo-Boolean Constraint Encodings for Conjunctive Normal Form and their Applications
… e.g. the number of clauses or if generalized arc consistency (GAC) is maintained during the search for a solution. There are various PB encodings that try to optimize or balance these properties. This thesis is about such encodings. For a better understanding of the research field an overview …
-
Designing and Optimizing Representations for Non-Binary Constraints
… are stronger than GAC and have stronger search space reduction, but are more costly to enforce. Thus, only a few practical higher-order consistency algorithms have been designed. We propose to transform one CSP into another, so that higher-order consistencies can be enforced through GAC on …
Page 1 of 2