Retour

G-2004-48

Merging the Local and Global Approaches to Probabilistic Satisfiability

et

référence BibTeX

The probabilistic satisfiability problem is to verify the consistency of a set of probability values or intervals for logical propositions. The (tight) probabilistic entailment problem is to find best bounds on the probability of an additional proposition. The local approach to these problems applies rules on small sets of logical sentences and probabilities to tighten given probability intervals. The global approach uses linear programming to find best bounds. We show that merging these approaches is profitable to both: local solutions can be used to find global solutions more quickly through stabilized column generation, and global solutions can be used to confirm or refute the optimality of the local solutions found. As a result, best bounds are found, together with their step-by-step justification.

, 27 pages

Ce cahier a été révisé en mars 2007

Axes de recherche

Applications de recherche

Publication

Merging the local and global approaches to probabilistic satisfiability
et
International Journal of Approximate Reasoning, 47(2), 125–140, 2008 référence BibTeX