AAAI Publications, Seventh Annual Symposium on Combinatorial Search

Font Size: 
Evaluating Weighted DFS Branch and Bound over Graphical Models
Natalia Flerova, Radu Marinescu, Rina Dechter

Last modified: 2014-07-02


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 Cw · 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.


weighted search; anytime search; graphical models; optimization; heuristic search

Full Text: PDF