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.
Published November 1989 , 33 pages
This cahier was revised in December 1990