Using weighted MAX-SAT engines to solve MPE
James D. Park · 2002
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. SAT is the problem of taking a set of clauses with associated weights, and finding the instantiation that produces the largest sum of the weights of satisfied clauses. Weighted MAX-SAT is used for example to resolve conflicts in a knowledge base. Finding approximate solutions to weighted MAX-SAT has received significant research attention, and novel algorithms have been developed that have proved to be very successful. This paper investigates using local search algorithms developed for weighted MAX-SAT and applying them to approximately solve MPE. Local search is a general optimization technique which can be used alone or as a method for improving solutions found by other approximation methods. We compare two successful local search algorithms in the MAX-SAT domain ( Discrete Lagrangian Multipliers (Wah & Shang 1997), and Guided Local Search (Mills & Tsang 2000) ) to the local search method proposed for MPE (Kask &Dechter 1999). For large problems, the MAX-SAT algorithms proved to be significantly more powerful, typically providing instantiations that are orders of magnitude more probable. The paper is organized as follows: First, we formally introduce the MPE and MAX-SAT problems. Then we present the reduction of MPE to MAX-SAT. We then introduce the MAX-SAT algorithms that will be evaluated. Finally, we provide experimental results comparing the solution quality of MPE approximations using the MAX-SAT methods to the previously proposed local search method developed for MPE.