Groupe d’études et de recherche en analyse des décisions

G-89-40

Column Generation Methods for Probabilistic Logic

, et

Nilsson recently introduced a rigorous semantic generalization of logic in which the truth values of sentences are probability values. This led to state precisely several basic problems of Artificial Intelligence, a paradigm of which is probabilistic satisfiability (PSAT): determine, given a set of clauses and probabilities that these clauses are true, whether these probabilities are consistent. We consider several extensions of this model involving intervals on probability values, conditional probabilities and minimal modifications of probability values to ensure satisfiability. Investigating further an approach of Georgakopoulos, Kavvadias and Papadimitriou, we propose a column generation algorithm which allows to solve exactly all these extensions. Computational experience shows that large problems, with up to 140 variables and 300 clauses, may be solved in reasonable time.

, 33 pages

Ce cahier a été révisé en décembre 1990