We solve constraint satisfaction problems through translation to answer set programming (ASP). Our reformulations have the property that unit-propagation in the ASP solver achieves well defined local consistency properties like arc, bound and range consistency. Experiments demonstrate the computational value of this approach.
In a translation-based approach, all parts of the model are mapped into a single constraint language for which highly efficient off-the-shelf solvers are available. Hence, related work has mostly focussed on the translation of constraints to SAT (cf. @cite_6 @cite_23 ). Translation into ASP, however, can be more general than translation into SAT: Every nogood can be syntactically represented by a clause, but other ASP constructs are also possible, such as cardinality and weight constraints @cite_0 . ASP was put forward as a novel paradigm for modelling and solving CSP in @cite_14 , where straightforward encodings to represent generic constraints via either allowed or forbidden combination of values has been presented. Preliminary work on translating CASP into ASP was conducted in @cite_11 , but they did not consider what level of consistency was achieved by their translation.
@cite_14 @cite_6 @cite_0 @cite_23 @cite_11
1550483759 2097646889 1569435728 2126442135
I describe and study the 'support encoding' of binary constraint satisfaction problems (CSP's) into boolean satisfiability (SAT). This is based on work by Kasif in 1990, in which clauses encode support information, rather than the encoding of conflicts in the standard 'direct encoding'. This enables arc consistency in the original CSP to be established by propagation in the translated SAT instance, providing an optimal worst case time algorithm for arc consistency [14]. I prove that the DP algorithm in SAT applied to the suport encoding behaves exactly like the MAC algorithm in CSP's. Using the SAT solver Chaff, I show that the support encoding can be used effectively to solve hard instances of random binary CSP's, and more effectively than the direct encoding on hard instances. Finally, I show that the local search algorithm WalkSAT can perform many times better on the support encoding than on the direct encoding. By the breakthrough work of Hastad [J ACM 48(4) (2001), 798–859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin, and Max E4-Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2-CSP); as a corollary of the celebrated Goemans-Williamson algorithm [J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2-CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2-CSPs over larger, non-Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2-SAT to domains of size d, can be approximated to a factor better than (1 − 1 d2). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not-All-Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d ≥ 3. In the Boolean case, Not-All-Equal Sat with three variables per constraint is equivalent to Max 2-SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2-SAT can be reduced to Not-All-Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2-CSPs called regular 2-CSPs can all be approximated beyond their random assignment threshold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004 The paper introduces a collection of knowledge representation languages, ν(C), parametrised over a class C of constraints. ν(C) is an extension of both CR-Prolog and CASP allowing the separation of a program into two parts: a regular program of CR-Prolog and a collection of denials whose bodies contain constraints from C with variables ranging over large domains. We study an instance AC0 from this family where C is a collection of constraints of the form X - Y > K. We give brief implementation details of an algorithm computing the answer sets of programs of AC0 which does not ground constraint variables and tightly couples the "classical" ASP algorithm with an algorithm checking consistency of difference constraints. We present several examples to show the methodology of representing knowledge in AC0. The work makes it possible to solve problems which could not be solved by pure ASP or constraint solvers. We present a simple probabilistic algorithm for solving k-SAT and more generally, for solving constraint satisfaction problems (CSP). The algorithm follows a simple local search paradigm (S. , 1992): randomly guess an initial assignment and then, guided by those clauses (constraints) that are not satisfied, by successively choosing a random literal from such a clause and flipping the corresponding bit, try to find a satisfying assignment. If no satisfying assignment is found after O(n) steps, start over again. Our analysis shows that for any satisfiable k-CNF-formula with n variables this process has to be repeated only t times, on the average, to find a satisfying assignment, where t is within a polynomial factor of (2(1-1 k)) sup n . This is the fastest (and also the simplest) algorithm for 3-SAT known up to date. We consider also the more general case of a CSP with n variables, each variable taking at most d values, and constraints of order l, and analyze the complexity of the corresponding (generalized) algorith m. It turns out that any CSP can be solved with complexity at most (d spl middot (1-1 l)+ spl epsiv ) sup n .