Column Generation Methods for Probabilistic Logic

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...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 1991-05, Vol.3 (2), p.135-148
Main Authors: Jaumard, Brigitte, Hansen, Pierre, Poggi de Aragao, Marcus
Format: Article
Language:English
Subjects:
artificial intelligence: expert systems
column generation
programming: integer
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 G. Georgakopoulos, D. Kavvadias and C. H. 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. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
ISSN:0899-1499
1526-5528
2326-3245
DOI:10.1287/ijoc.3.2.135