A linear programming approach to reasoning about probabilities. (English) Zbl 0878.68034

Kavvadias, Dimitris; Papadimitriou, Christos H.

Ann. Math. Artif. Intell. 1, No. 1-4, 189-205 (1990).

Summary: We continue our study of the following computational problem proposed by Nilsson: Several clauses (Boolean functions of several variables) are given, and for each clause the probability that the clause is true is specified. We are asked whether these probabilities are consistent. They are if there is a probability distribution on the truth assignments such that the probability of each clause is the measure of its satisfying set of assignments. Since this is a generalization of the satisfiability problem of predicate calculus, it is immediately NP-hard. We showed previously certain restricted cases of the problem to be NP-complete, and used the Ellipsoid Algorithm to show that a certain special case is in P. In this paper, we use the Simplex method, column generation techniques, and variable-depth local search to derive an effective heuristic for the general problem. Experiments show that our heuristic performs successfully on instances with many dozens of variables and clauses. We also prove several interesting complexity results.

MSC:

68N17	Logic programming
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

predicate calculus; satisfiability problem

References:

[1]	T. Brun, J. Desrosiers, P. Hansen and H. Jaumard,Proc. Symp. on Mathematical Progress, Tokyo (1988).
[2]	G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, 1963).
[3]	G.B. Dantzig and P. Wolfe, Decomposition principle for linear programming, Oper. Res. 8 (1960) 101-111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[4]	R. Duda and R. Reboh, AI and decision making: The PROSPECTOR experience, in:AI Applications in Business, ed. W. Reitman (1984) pp. 111-147.
[5]	R. Fagin, J. Halpern and N. Megiddo,Proc. IEEE Conf. on Logics in Computer Science (1988).
[6]	M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, 1979). · Zbl 0411.68039
[7]	M.R. Garey, D.S. Johnson and L.J. Stockmeyer, Some simplified NP-complete problems, Theor. Comp. Sci. 1 (1976) 237-267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[8]	M. Genesareth and N. Nilsson,Logical Foundations for AI (Morgan Kaufmann, 1987).
[9]	G. Georgakopoulos, D. Kavvadias, and C.H. Papadimitriou, Probabilistic satisfiability, J. Complexity (1988). · Zbl 0647.68049
[10]	D. Goldfarb and J.K. Reid, A practicable steepest-edge Simplex algorithm, Math. Progr. 12 (1977) 361-371. · Zbl 0443.90058 · doi:10.1007/BF01593804
[11]	P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation, and persistency in quadratic 0-1 optimization, Math. Prog. 28 (1984) 121-155. · Zbl 0574.90066 · doi:10.1007/BF02612354
[12]	D. Kavvadias, Complexity and heuristic methods for probabilistic logic, Ph.D. Dissertation, University of Patras (November 1988) (in Greek).
[13]	B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, BSTJ 49 (1970) 291-307. · Zbl 0333.05001
[14]	S. Lin and B.W. Kernighan, An effective heuristic for the traveling salesman problem, Oper. Res. 21 (1973) 498-516. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[15]	N. Nilsson, Probabilistic logic, Artificial Intelligence (1986). · Zbl 0589.03007
[16]	C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, 1983). · Zbl 0944.90066
[17]	B. Rothfarb, H. Frank, D.M. Rosenbaum, K. Steiglitz and D.J. Kleitman, Optimal design of offshore natural-gas pipeline systems, Oper. Res. 18 (1970) 992-1020. · doi:10.1287/opre.18.6.992
[18]	G. Shafer,A Mathematical Theory of Evidence (Princeton, Univ. Press, 1976). · Zbl 0359.62002
[19]	H.E. Shortliffe and B.G. Buneman, A model of inexact reasoning in medicine, Math. Biosci. 3 (1975) 351-379. · doi:10.1016/0025-5564(75)90047-4
[20]	L.A. Zadeh, Fuzzy sets, Information and Control 8 (1971) 338-353. · Zbl 0139.24606 · doi:10.1016/S0019-9958(65)90241-X