We study here a CSP decomposition method introduced in [9] and called Cyclic-Clustering. While [9] only presents the principles of the method, this paper explains how this method can be made operational by exploiting ...
详细信息
ISBN:
(纸本)076952236X
We study here a CSP decomposition method introduced in [9] and called Cyclic-Clustering. While [9] only presents the principles of the method, this paper explains how this method can be made operational by exploiting good properties of triangulated induced subgraphs. After we give formal results which show that Cyclic-Clustering proposes a time-space trade-off wrt. theoretical complexities. Finally, we present some preliminary experiments which show that Cyclic-Clustering may be efficient in practice.
the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general ...
详细信息
ISBN:
(纸本)3540232419
the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general intractable, it may be restricted by requiring the "target structure" B to be fixed;denote this restriction by CSP(B). In recent years, much effort has been directed towards classifying the complexity of all problems CSP(B). the acquisition of CSP(B) tractability results has generally proceeded by isolating a class of relational structures B believed to be tractable, and then demonstrating a polynomial-time algorithm for the class. In this paper, we introduce a new approach to obtaining CSP(B) tractability results: instead of starting with a class of structures, we start with an algorithm called look-ahead arc consistency, and give an algebraic characterization of the structures solvable by our algorithm. this characterization is used both to identify new tractable structures and to give new proofs of known tractable structures.
We study here a CSP decomposition method introduced in [P. Jegou (1990)] and called cyclic-clustering. While [P. Jegou (1990)] only presents the principles of the method, this work explains how this method can be made...
详细信息
We study here a CSP decomposition method introduced in [P. Jegou (1990)] and called cyclic-clustering. While [P. Jegou (1990)] only presents the principles of the method, this work explains how this method can be made operational by exploiting good properties have triangulated induced subgraphs. After, we give formal results, which show that cyclic-clustering proposes a time-space trade-off w.r.t. theoretical complexities. Finally, we present some preliminary experiments, which show that cyclic-clustering may be efficient in practice.
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furt...
ISBN:
(纸本)3540232419
When solving constraint Satisfaction Problems (CSPs), it is desirable to find multiple solutions, or to find solutions that are robust, allowing us to modify the values of variables without breaking the solution. Furthermore, we would like to be able to represent these multiple solutions in a compact manner. We present a method for improving the performance of, and solutions returned by, stochastic local search using maximal independent sets1 of the constraint graph. Given an independent set, this information can be used to significantly speed up the process of solving a CSP by reducing the search space. the CSP is partitioned into two sets of variables I and [`(I)]\bar{I}, where I is a maximal independent set of the constraint graph. In this way, search is concentrated only on the variables of [`(I)]\bar{I}, reducing the search space by a factor exponential in the size of I. Also this technique can provide multiple solutions in a compact form with no extra cost, since if we find a set of valid domain values for each variable in I, every element of the Cartesian product of these sets is a solution to the CSP. We focus on exploiting this information in local search. this technique is limited to low-density graphs, since dense graphs are less likely to contain a large independent set. the resulting solutions are robust with respect to the variables in the independent set. We compare the technique with WalkSAT, as defined for CSPs by [2], on low-density random CSP instances generated according to model B, with16 variables, domain size 8, tightness 0.3 and density 0.1. the average CPU run-time for WalkSAT was 96.5 seconds, while the average for WalkSAT_IS was 0.36 seconds. Also, while WalkSAT returns one solution, the average number of solutions returned by WalkSAT_IS per instance was 47,536,305 solutions this is a dramatic improvement in performance, as well as in the number of solutions returned. this technique falls in the category of algorithms exploiting backdoor
Arc consistency plays a central role in solving constraint Satisfaction Problems. this is the reason why many algorithms have been proposed to establish it. Recently, an algorithm called AC2001 and AC3.1 has been inde...
详细信息
We present an interface between the ECLiPSe constraint logic programming system and the GAP computational abstract algebra system. the interface provides a method for efficiently dealing with large numbers of symmetri...
详细信息
One of the key factors in the efficiency of backtracking algorithms is the rule they use to decide on which variable to branch next (namely, the variable ordering heuristics). In this paper, we give a formulation of d...
详细信息
the Stable Marriage problem (SM) is an extensively-studied combinatorial problem with many practical applications. In this paper we present two encodings of an instance I of SM as an instance J of a constraint Satisfa...
详细信息
this paper describes the architecture and implementation of a constraint-based framework for rapid prototyping of distributed applications such as virtual simulations, collaborations and games. Our framework integrate...
详细信息
暂无评论