The paper focuses on finding the m best solutions to combinatorial optimization problems using best-first or depth-first branch and bound search. Specifically, we present a new algorithm m-A*, extending the well-known A* to the m-best task, and for the first time prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since best-first algorithms require extensive memory, we also extend the memory-efficient depth-first branch and bound to the m-best task. We adapt both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task.

Weighted search was explored significantly in recent years for path-finding problems, but until now was barely considered for optimization tasks such as MPE/MAP and Weighted CSPs. An important virtue of weighted search schemes, especially in the context of anytime search, is that they are w-optimal, i.e. when terminated, they return a weight w, and a solution cost C, such that C ≤ w · C*, where C* is the optimal cost. In this paper we introduce Weighted Branch and Bound (WBB) for graphical models and provide a broad empirical evaluation of its performance compared with one of the best unweighted anytime search scheme, BRAOBB (won Pascal 2011 competition). We also compare against weighted best-first (WBF). Our results show that W BB can be superior to both unweighted BB and to weighted BF on a significant number of instances. We also illustrate the benefit of weighted search in providing suboptimality relative error bounds.

The paper focuses on finding the m best solutions to combinatorial optimization problems using Best-First or Branchand- Bound search. Specifically, we present m-A*, extending the well-known A* to the m-best task, and prove that all its desirable properties, including soundness, completeness and optimal efficiency, are maintained. Since Best-First algorithms have memory problems, we also extend the memoryefficient Depth-First Branch-and-Bound to the m-best task. We extend both algorithms to optimization tasks over graphical models (e.g., Weighted CSP and MPE in Bayesian networks), provide complexity analysis and an empirical evaluation. Our experiments with 5 variants of Best-First and Branch-and-Bound confirm that Best-First is largely superior when memory is available, but Branch-and-Bound is more robust, while both styles of search benefit greatly when the heuristic evaluation function has increased accuracy.