A Dynamic Approach for MPE and Weighted MAX-SAT

Sang, Tian; Beame, Paul; Kautz, Henry A.

A Dynamic Approach for MPE and Weighted MAX-SAT

Download BibTeX Cite

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.

Tian Sang, Paul Beame, and Henry A. Kautz. 2007. A Dynamic Approach for MPE and Weighted MAX-SAT. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 173–178. https://ijcai.org/proceedings/2007/26

@inproceedings{ijcai2007p26,
  title     = {A Dynamic Approach for MPE and Weighted MAX-SAT},
  author    = {Sang, Tian and Beame, Paul and Kautz, Henry A.},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {173--178},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/26},
}

TY  - CPAPER
TI  - A Dynamic Approach for MPE and Weighted MAX-SAT
AU  - Sang, Tian
AU  - Beame, Paul
AU  - Kautz, Henry A.
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 173
EP  - 178
UR  - https://ijcai.org/proceedings/2007/26
ER  -