Abstract
The paper explores the power of two systematic Branch and Bound search algorithms that exploit partition-based heuristics, BBBT (a recent 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. We show empirically that the new Branch and Bound algorithm, BBBT is powerful and is sometimes superior to BBMB in that it can exploit bounded-space information more effectively. 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. This is in contrast to 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 among the best performing algorithms for solving the MPE task.