Systematic vs. Non-Systematic Algorithms for Solving the MPE Task

Abstract

The paper explores the power of two systematic Branch and Bound search algorithms that exploit partition-based heuristics, BBBT (a new algorithm 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) and compares them against a number of popular local search algorithms for the MPE problem as well as against the recently popular iterative belief propagation algorithms. We show empirically that the new Branch and Bound algorithm, BBBT demonstrates tremendous pruning of the search space far beyond its predecessor, BBMB which translates to impressive time saving for some classes of problems. Second, when viewed as approximation schemes, BBBT/BBMB together are highly competitive with the best known SLS algorithms and are superior, especially when the domain sizes increase beyond 2. The results also show that the class of belief propagation algorithms can outperform SLS, but they are quite inferior to BBMB/BBBT. As far as we know, BBBT/BBMB are currently among the best performing algorithms for solving the MPE task.