Petak, 28. maj 2001. u 12h:

Pierre Hansen, Gerad, Ecole des Hautes Etudes Commerciales, Montreal and Hong Kong Polytechnic
PROBABILISTIC SATISFIABILITY

Probabilistic satisfiability is a basic model for reasoning under uncertainty which, in contrast with many AI systems, agrees with the theories of logic and of probabilities. It is due to George Boole, in the last part of his famous book of 1854 on "An investigation of the Laws of Thought". The decision version is as follows: given m logical sentences S1,S2,...,Sm defined on n logical variables x1,x2,...,xn, together with their probabilities pi1,pi2,...,pim of being true determine if these probabilities are coherent (or which "conditions of possible experience " they should satisfy for this to be the case). The optimisation form assumes one more sentence Sm+1 is given on the probability of which best possible lower and upper bounds are to be found. We survey research on this problem from Boole to the present. We show in particular that mathematical programming leads to both analytical and numerical efficient solution procedures. Column generation, with nonlinear 0-1 programming make it possible to solve instances with over 1000 sentences and/or variables.