### Sparse Message Passing Algorithms for Weighted Maximum Satisfiability

Aron Culotta, Andrew McCallum, Bart Selman, and Ashish Sabharwal, NESCAI 2007

#### Abstract

Weighted maximum satisfiability is a well-studied problem that has important
applicability to artificial intelligence (for instance, MAP inference in
Bayesian networks). General-purpose stochastic search algorithms have proven
to be accurate and efficient for large problem instances; however, these
algorithms largely ignore structural properties of the input. For example,
many problems are highly *clustered*, in that they contain a collection of
loosely coupled subproblems (e.g. pipelines of NLP tasks). In this paper, we
propose a message passing algorithm to solve weighted maximum satisfiability
problems that exhibit this clustering property. Our algorithm fuses local
solutions to each subproblem into a global solution by iteratively passing
summary information between clusters and recomputing local solutions. Because
the size of these messages can become unwieldy for large problems, we explore
several message compression techniques to transmit the most valuable
information as compactly as possible. We empirically compare our algorithm
against a state-of-the-art stochastic solver and show that for certain classes
of problems our message passing algorithm finds significantly better
solutions.

#### Citation

```
@inproceedings{culotta07sparse,
author = {Aron Culotta and Andrew McCallum and Bart Selman and Ashish Sabharwal},
title = {Sparse Message Passing Algorithms for Weighted Maximum Satisfiability},
booktitle = {New England Student Colloquium on Artificial Intelligence (NESCAI)},
address = {Ithaca, NY},
year = {2007},
}
```