Publication
Lifted Message Passing for Satisfiability
Fabian Hadiji; Kristian Kersting; Babak Ahmadi
In: Statistical Relational Artificial Intelligence, Papers from the 2010 AAAI Workshop. AAAI Conference on Artificial Intelligence (AAAI-2010), July 12, Atlanta, Georgia, USA, AAAI Technical Report, Vol. WS-10-06, AAAI, 2010.
Abstract
Unifying logical and probabilistic reasoning is a longstanding goal of AI. While recent work in lifted belief propagation, handling whole sets of indistinguishable objects together, are promising steps towards achieving this goal that even scale to realistic domains, they are not tailored towards solving combinatorial problems such as determining the satisfiability of Boolean formulas. Recent results, however, show that certain other message passing algorithms, namely, survey propagation, are remarkably successful at solving such problems. In this paper, we propose the first lifted variants of survey propagation and its simpler version warning propagation. Our initial experimental results indicate that they are faster than using lifted belief propagation to determine the satisfiability of Boolean formulas.