---
title: "A Dynamic Approach for MPE and Weighted MAX-SAT"
authors:
  - "Tian Sang"
  - "Paul Beame"
  - "Henry A. Kautz"
doi: ""
url: "https://ijcai.org/proceedings/2007/26"
pdf: "https://ijcai.org/proceedings/2007/0026.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "173-178"
track: ""
keywords:
---

# A Dynamic Approach for MPE and Weighted MAX-SAT

Tian Sang, Paul Beame, Henry A. Kautz

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 173-178.

## Abstract

The problem of Most Probable Explanation (MPE) arises in the scenario of probabilistic inference: finding an assignment to all variables that has the maximum likelihood given some evidence. We consider the more general CNF-based MPE problem, where each literal in a CNF-formula is associated with a weight. We describe reductions between MPE and weighted MAX-SAT, and show that both can be solved by a variant of weighted model counting. The MPE-SAT algorithm is quite competitive with the state-of-the-art MAX-SAT, WCSP, and MPE solvers on a variety of problems.