Using Weighted MAX-SAT Engines to Solve MPE

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Satisfiability

Logical and probabilistic reasoning are closely related. Many examples in each group have natural analogs in the other. One example is the strong relationship between weighted MAX-SAT and MPE. This paper presents a simple reduction of MPE to weighted MAX-SAT. It also investigates approximating MPE by converting it to a weighted MAX-SAT problem, then using the incomplete methods for solving weighted MAX-SAT to generate a solution. We show that converting MPE problems to MAX-SAT problems and using a method designed for MAX-SAT to solve them often produces solutions that are vastly superior to the previous local search methods designed directly for the MPE problem.