Systematic vs. Non-systematic Algorithms for Solving the MPE Task
  The paper continues the study of partitioning based inference of heuristics
for search in the context of solving the Most Probable Explanation task in
Bayesian Networks. We compare two systematic Branch and Bound search
algorithms, BBBT (for which the heuristic information is constructed during
search and allows dynamic variable/value ordering) and its predecessor BBMB
(for which the heuristic information is pre-compiled), against a number of
popular local search algorithms for the MPE problem. We show empirically that,
when viewed as approximation schemes, BBBT/BBMB are superior to all of these
best known SLS algorithms, especially when the domain sizes increase beyond 2.
This is in contrast with the performance of SLS vs. systematic search on
CSP/SAT problems, where SLS often significantly outperforms systematic
algorithms. As far as we know, BBBT/BBMB are currently the best performing
algorithms for solving the MPE task.
