Solving satisfiability problems with preferences

Propositional satisfiability (SAT) is a success story in Computer Science and Artificial Intelligence: SAT solvers are currently used to solve problems in many different application domains, including planning and formal verification. The main reason for this success is that modern SAT solvers can successfully deal with problems having millions of variables. All these solvers are based on the Davis–Logemann–Loveland procedure (dll). In its original version, dll is a decision procedure, but it can be very easily modified in order to return one or all assignments satisfying the input set of clauses, assuming at least one exists. However, in many cases it is not enough to compute assignments satisfying all the input clauses: Indeed, the returned assignments have also to be “optimal” in some sense, e.g., they have to satisfy as many other constraints—expressed as preferences—as possible. In this paper we start with qualitative preferences on literals, defined as a partially ordered set (poset) of literals. Such a poset induces a poset on total assignments and leads to the definition of optimal model for a formula ψ as a minimal element of the poset on the models of ψ. We show (i) how dll can be extended in order to return one or all optimal models of ψ (once converted in clauses and assuming ψ is satisfiable), and (ii) how the same procedures can be used to compute optimal models wrt a qualitative preference on formulas and/or wrt a quantitative preference on literals or formulas. We implemented our ideas and we tested the resulting system on a variety of very challenging structured benchmarks. The results indicate that our implementation has comparable performances with other state-of-the-art systems, tailored for the specific problems we consider.     

Tractability through symmetries in propositional calculus

Many propositional calculus problems — for example the Ramsey or the pigeon-hole problems — can quite naturally be represented by a small set of first-order logical clauses which becomes a very large set of propositional clauses when we substitute the variables by the constants of the domainD. In many cases the set of clauses contains several symmetries, i.e. the set of clauses remains invariant under certain permutations of variable names. We show how we can shorten the proof of such problems. We first present an algorithm which detects the symmetries and then we explain how the symmetries are introduced and used in the following methods: SLRI, Davis and Putnam and semantic evaluation. Symmetries have been used to obtain results on many known problems, such as the pigeonhole, Schur's lemma, Ramsey's, the eight queen, etc. The most interesting one is that we have been able to prove for the first time the unsatisfiability of Ramsey's problem (17 vertices and three colors) which has been the subject of much research.     

Reducing the size of resolution proofs in linear time

DPLL-based SAT solvers progress by implicitly applying binary resolution. The resolution proofs that they generate are used, after the SAT solver’s run has terminated, for various purposes. Most notable uses in formal verification are: extracting an unsatisfiable core, extracting an interpolant, and detecting clauses that can be reused in an incremental satisfiability setting (the latter uses the proof only implicitly, during the run of the SAT solver). Making the resolution proof smaller can benefit all of these goals: it can lead to smaller cores, smaller interpolants, and smaller clauses that are propagated to the next SAT instance in an incremental setting. We suggest two methods that are linear in the size of the proof for doing so. Our first technique, called Recycle-Units uses each learned constant (unit clause) (x) for simplifying resolution steps in which x was the pivot, prior to when it was learned. Our second technique, called   simplifies proofs in which there are several nodes in the resolution graph, one of which dominates the others, that correspond to the same pivot. Our experiments with industrial instances show that these simplifications reduce the core by ≈5% and the proof by ≈13%. It reduces the core less than competing methods such as run- till- fix, but whereas our algorithms are linear in the size of the proof, the latter and other competing techniques are all exponential as they are based on SAT runs. If we consider the size of the proof (the resolution graph) as being polynomial in the number of variables (it is not necessarily the case in general), this gives our method an exponential time reduction comparing to existing tools for small core extraction. Our experiments show that this result is evident in practice more so for the second method: rarely it takes more than a few seconds, even when competing tools time out, and hence it can be used as a cheap proof post-processing procedure.     

Answering atomic queries in indefinite deductive databases

Answering queries in indefinite systems is a difficult problem both computationally, since it involves non-Horn clauses and factoring, and conceptually, concerning producing beliefs for formulas not derivable from the system. to provide a basis for reasonable beliefs, we propose new criteria as an alternative to the Full Information Principle. Then an approach to producing stable beliefs, called Plausible World Assumption (PWA), is introduced. It is shown how a set of non-Horn clauses can be transformed into a set of so called singleton-head-rules such that evaluation of a given query is reduced to processing of a set of Horn clauses relevant to the query. Finally, algorithms are presented for computing facts and beliefs for atomic queries in accord with the PWA. This method is shown to be more efficient than the known techniques for query evaluation in indefinite systems.     

Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.     

Inductive expansion: A calculus for verifying and synthesizing functional and logic programs

Guarded Horn clauses over a many-sorted polymorphic signature provide a powerful syntax for design specifications. Expressed as a set of positive Gentzen clauses with a common guard, requirements to such a specification can be proved top-down by inductive expansion: conclusions and generators of the clauses are transformed via resolution and paramodulation upon axioms, lemmas and induction hypotheses into the guard. Case distinctions are generated when axioms or lemmas are applied in parallel. They split the proof into subexpansions, which are later rejoined by applying disjunctive lemmas. Induction orderings need not be selected before redices for induction hypotheses have been created.The controlled expansion of requirements to a function (or predicate) may produce axioms representing a program for that function. This generalizes traditional approaches to program synthesis such as fold& unfold, divide&conquer or deductive tableaus. Ground confluent and strongly terminating design specifications yield decidable criteria for constructors and unsolvable goals and thus reduce the search space of inductive expansion.     

On Skolemization in constrained logics

Quantification in first-order logic always involves all elements of the universe. However, it is often more natural to just quantify over those elements of the universe which satisfy a certain condition. Constrained logics therefore provide restricted quantifiers _X:R F and _X:R F whereX is a set of variables, and which can be read as F holds for all elements satisfying the restrictionR and F holds if there exists an element which satisfiesR. In order to test satisfiability of a set of such formulas by means of an appropriately extended resolution principle, one needs a procedure which transforms them into a set of clauses with constraints. Such a procedure essentially differs from the classical transformation of first-oder formulas into a set of clauses, in particular since quantification over the empty set may occur and since the needed Skolemization procedure has to take the restrictions of restricted quantifiers into account. In the first part of this article we present a procedure that transforms formulas with restricted quantifiers into a set of clauses with constraints while preserving satisfiability. The thus obtained clauses are of the formC R whereC is an ordinary clause andR is a restriction, and can be read as C holds ifR holds. These clauses can now be tested on unsatisfiability via the existingconstrained resolution principle. In the second part we generalize the constrained resolution principle in such a way that it allows for further optimization, and we introduce a combination of unification and constraint solving that can be employed to instantiate this kind of optimization.     

Constraint-based probabilistic modeling for statistical abduction

We introduce a new framework for logic-based probabilistic modeling called constraint-based probabilistic modeling which defines CBPMs (constraint-based probabilistic models) , i.e. conditional joint distributions P(⋅∣KB) over independent propositional variables constrained by a knowledge base KB consisting of clauses. We first prove that generative models such as PCFGs and discriminative models such as CRFs have equivalent CBPMs as long as they are discrete. We then prove that CBPMs in infinite domains exist which give existentially closed logical consequences of KB probability one. Finally we derive an EM algorithm for the parameter learning of CBPMs and apply it to statistical abduction.     

Mining changing regions from access-constrained snapshots: a cluster-embedded decision tree approach

Change detection on spatial data is important in many applications, such as environmental monitoring. Given a set of snapshots of spatial objects at various temporal instants, a user may want to derive the changing regions between any two snapshots. Most of the existing methods have to use at least one of the original data sets to detect changing regions. However, in some important applications, due to data access constraints such as privacy concerns and limited data online availability, original data may not be available for change analysis. In this paper, we tackle the problem by proposing a simple yet effective model-based approach. In the model construction phase, data snapshots are summarized using the novel cluster-embedded decision trees as concise models. Once the models are built, the original data snapshots will not be accessed anymore. In the change detection phase, to mine changing regions between any two instants, we compare the two corresponding cluster-embedded decision trees. Our systematic experimental results on both real and synthetic data sets show that our approach can detect changes accurately and effectively. Irene Pekerskaya’s and Jian Pei’s research is supported partly by National Sciences and Engineering Research Council of Canada and National Science Foundation of the US, and a President’s Research Grant and an Endowed Research Fellowship Award at Simon Fraser University. Ke Wang’s research is supported partly by Natural Sciences and Engineering Research Council of Canada. All opinions, findings, conclusions and recommendations in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.     

Positive Unit Hyperresolution Tableaux and Their Application to Minimal Model Generation

Minimal Herbrand models of sets of first-order clauses are useful in several areas of computer science, for example, automated theorem proving, program verification, logic programming, databases, and artificial intelligence. In most cases, the conventional model generation algorithms are inappropriate because they generate nonminimal Herbrand models and can be inefficient. This article describes an approach for generating the minimal Herbrand models of sets of first-order clauses. The approach builds upon positive unit hyperresolution (PUHR) tableaux, that are in general smaller than conventional tableaux. PUHR tableaux formalize the approach initially introduced with the theorem prover SATCHMO. Two minimal model generation procedures are described. The first one expands PUHR tableaux depth-first relying on a complement splitting expansion rule and on a form of backtracking involving constraints. A Prolog implementation, named MM-SATCHMO, of this procedure is given, and its performance on benchmark suites is reported. The second minimal model generation procedure performs a breadth-first, constrained expansion of PUHR (complement) tableaux. Both procedures are optimal in the sense that each minimal model is constructed only once, and the construction of nonminimal models is interrupted as soon as possible. They are complete in the following sense: The depth-first minimal model generation procedure computes all minimal Herbrand models of the considered clauses provided these models are all finite. The breadth-first minimal model generation procedure computes all finite minimal Herbrand models of the set of clauses under consideration. The proposed procedures are compared with related work in terms of both principles and performance on benchmark problems.     

Learning Decision Lists

This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples. More precisely, this result is established for k-;DL – the set of decision lists with conjunctive clauses of size k at each decision. Since k-DL properly includes other well-known techniques for representing Boolean functions such as k-CNF (formulae in conjunctive normal form with at most k literals per clause), k-DNF (formulae in disjunctive normal form with at most k literals per term), and decision trees of depth k, our result strictly increases the set of functions that are known to be polynomially learnable, in the sense of Valiant (1984). Our proof is constructive: we present an algorithm that can efficiently construct an element of k-DL consistent with a given set of examples, if one exists.     

Choosing a Random Peer in Chord

We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency O(log n) and send O(log n) messages. Moreover, we show empirically that the average latency and message cost of Arc Length is 10.01log n and that the average latency and message cost of Peer Count is 20.02log n. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance. Research of S. Lewis, J. Saia and M. Young was partially supported by NSF grant CCR-0313160 and Sandia University Research Program grant No. 191445.     

Complexity of computing with extended propositional logic programs

In this paper we introduce the notion of anF-program, whereF is a collection of formulas. We then study the complexity of computing withF-programs.F-programs can be regarded as a generalization of standard logic programs. Clauses (or rules) ofF-programs are built of formulas fromF. In particular, formulas other than atoms are allowed as building blocks ofF-program rules. Typical examples ofF are the set of all atoms (in which case the class of ordinary logic programs is obtained), the set of all literals (in this case, we get the class of logic programs with classical negation [9]), the set of all Horn clauses, the set of all clauses, the set of all clauses with at most two literals, the set of all clauses with at least three literals, etc. The notions of minimal and stable models [16, 1, 7] of a logic program have natural generalizations to the case ofF-programs. The resulting notions are called in this paperminimal andstable answer sets. We study the complexity of reasoning involving these notions. In particular, we establish the complexity of determining the existence of a stable answer set, and the complexity of determining the membership of a formula in some (or all) stable answer sets. We study the complexity of the existence of minimal answer sets, and that of determining the membership of a formula in all minimal answer sets. We also list several open problems.This work was partially supported by National Science Foundation under grant IRI-9012902.This work was partially supported by National Science Foundation under grant CCR-9110721.     

Optimal External Memory Planar Point Enclosure

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log  _B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B ^1−ε ) disk blocks are needed for some constant ε>0. With linear space, the best obtainable query bound is O(log ₂ N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds. An extended abstract of this paper appeared in Proceedings of the 12th European Symposium on Algorithms (ESA’04), Bergen, Norway, September 2004, pp. 40–52. L. Arge’s research was supported in part by the National Science Foundation through RI grant EIA–9972879, CAREER grant CCR–9984099, ITR grant EIA–0112849, and U.S.-Germany Cooperative Research Program grant INT–0129182, as well as by the US Army Research Office through grant W911NF-04-01-0278, by an Ole Roemer Scholarship from the Danish National Science Research Council, a NABIIT grant from the Danish Strategic Research Council and by the Danish National Research Foundation. V. Samoladas’ research was supported in part by a grant co-funded by the European Social Fund and National Resources-EPEAEK II-PYTHAGORAS. K. Yi’s research was supported in part by the National Science Foundation through ITR grant EIA–0112849, U.S.-Germany Cooperative Research Program grant INT–0129182, and Hong Kong Direct Allocation Grant (DAG07/08).     

A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering

We consider a framework of sample-based clustering. In this setting, the input to a clustering algorithm is a sample generated i.i.d by some unknown arbitrary distribution. Based on such a sample, the algorithm has to output a clustering of the full domain set, that is evaluated with respect to the underlying distribution. We provide general conditions on clustering problems that imply the existence of sampling based clustering algorithms that approximate the optimal clustering. We show that the K-median clustering, as well as K-means and the Vector Quantization problems, satisfy these conditions. Our results apply to the combinatorial optimization setting where, assuming that sampling uniformly over an input set can be done in constant time, we get a sampling-based algorithm for the K-median and K-means clustering problems that finds an almost optimal set of centers in time depending only on the confidence and accuracy parameters of the approximation, but independent of the input size. Furthermore, in the Euclidean input case, the dependence of the running time of our algorithm on the Euclidean dimension is only linear. Our main technical tool is a uniform convergence result for center based clustering that can be viewed as showing that the effective VC-dimension of k-center clustering equals k. Editor: Olivier Bousquet and Andre Elisseeff A preliminary version of this work appeared in the proceedings of COLT’04 (Ben-David, 2004). This work is supported in part by the Multidisciplinary University Research Initiative (MURI) under the Office of Naval Research Contract N00014-00-1-0564.     

Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the k given sets. Such a partition defines a probability distribution, obtained by dividing each part size by n. The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat =log ₂ e bits ≃1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem. G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).     

A Protocol for a Private Set-Operation

A new private set-operation problem is proposed. Suppose there are n parties with each owning a secret set. Let one of them, say P, be the leader, S be P＇s secret set, and t （less than n - 1） be a threshold value. For each element w of S, if w appears more than t times in the rest parties＇ sets, then P learns which parties＇ sets include w, otherwise P cannot know whether w appears in any party＇s set. For this problem, a secure protocol is proposed in the semi-honest model based on semantically secure homomorphic encryption scheme, secure sharing scheme, and the polynomial representation of sets. The protocol only needs constant rounds of communication.     

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.