Search

It is well known that computing relative approximations of weighted counting queries such as the probability of evidence in a Bayesian network, the partition function of a Markov network, and the number of solutions of a constraint satisfaction problem is NP-hard. In this paper, we settle therefore on an easier problem of computing high-confidence lower bounds and propose an algorithm based on importance sampling and Markov inequality for it. However, a straight-forward application of Markov inequality often yields poor lower bounds because it uses only one sample. We therefore propose several new schemes that extend it to multiple samples. Empirically, we show that our new schemes are quite powerful, often yielding substantially higher (better) lower bounds than state-of-the-art schemes.

There are two main solving schemas for constraint satisfactionand optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size. In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter kcontrols the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by kand a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.

The paper compares two popular strategies for solving propositional satisfiability, backtracking searchand resolution, and analyzes the complexity of a directional resolution algorithm (DR) as a function of the “width” (w*) of the problem"s graph. Our empirical evaluation confirms theoretical prediction, showing that on low-w*problems DR is very efficient, greatly outperforming the backtracking-based Davis–Putnam–Logemann–Loveland procedure (DP). We also emphasize the knowledge-compilation properties of DR and extend it to a tree-clustering algorithm that facilitates query answering. Finally, we propose two hybrid algorithms that combine the advantages of both DR and DP. These algorithms use control parameters that bound the complexity of resolution and allow time/space trade-offs that can be adjusted to the problem structure and to the user"s computational resources. Empirical studies demonstrate the advantages of such hybrid schemes.

The paper focuses on evaluating constraint satisfaction search algorithms on application based random problem instances. The application we use is a well-studied problem in the electric power industry: optimally scheduling preventive maintenance of power generating units within a power plant. We show how these scheduling problems can be cast as constraint satisfaction problems and used to define the structure of randomly generated non-binary CSPs. The random problem instances are then used to evaluate several previously studied algorithms. The paper also demonstrates how constraint satisfaction can be used for optimization tasks. To find an optimal maintenance schedule, a series of CSPs are solved with successively tighter cost-bound constraints. We introduce and experiment with an “iterative learning” algorithm which records additional constraints uncovered during search. The constraints recorded during the solution of one instance with a certain cost-bound are used again on subsequent instances having tighter cost-bounds. Our results show that on a class of randomly generated maintenance scheduling problems, iterative learning reduces the time required to find a good schedule.

This position paper argues that extending the CSP model to a richer set of tasks such as, constraint optimization, probabilistic inference and decision theoretic tasks can be done within a unifying framework called ‘‘bucket elimination’’. The framework allows uniform hybrids for combining elimination and conditioning guided by the problem's structure and for explicating the tradeoffs between space and time and between time and accuracy.

In this paper we study the properties of the class of head-cycle-free extended disjunctive logic programs (HEDLPs), which includes, as a special case, all nondisjunctive extended logic programs. We show that any propositional HEDLP can be mapped in polynomial time into a propositional theory such that each model of the latter corresponds to an answer set, as defined by stable model semantics, of the former. Using this mapping, we show that many queries over HEDLPs can be determined by solving propositional satisfiability problems. Our mapping has several important implications: It establishes the NP-completeness of this class of disjunctive logic programs; it allows existing algorithms and tractable subsets for the satisfiability problem to be used in logic programming; it facilitates evaluation of the expressive power of disjunctive logic programs; and it leads to the discovery of useful similarities between stable model semantics and Clark's predicate completion.

This paper addresses the problem of computing the minimal models of a given CNF propositional theory. We present two groups of algorithms. Algorithms in the first group are efficient when the theory is almost Horn, that is, when there are few non-Horn clauses and/or when the set of all literals that appear positive in any non-Horn clause is small. Algorithms in the other group are efficient when the theory can be represented as an acyclic network of low-arity relations. Our algorithms suggest several characterizations of tractable subsets for the problem of finding minimal models.

This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h. It is shown that several known properties of A* retain their form (with the minmax of f playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm for achieving it. The main results of this paper relate to the class of algorithms that, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., h ≤ h*). On this class, A* is shown to be not optimal and it is also shown that no optimal algorithm exists, but if the performance tests are confirmed to cases in which the estimates are also consistent, then A* is indeed optimal. Additionally, A* is also shown to be optimal over a subset of the latter class containing all best-first algorithms that are guided by path-dependent evaluation functions.