Branch and Bound with Mini-Bucket Heuristics

Kalev Kask and Rina Dechter

The paper describes a new generic branch and bound scheme that uses heuristics generated mechanically by the mini-bucket approximation. The scheme is presented and evaluated for the Most Probable Explanation (MPE) task in Bayesian networks. We show that the mini-bucket scheme yields monotonic heuristics of varying strengths which cause different amounts of pruning during search. The resulting Branch and Bound with Mini-Bucket algorithm (BBMB), is evaluated using random networks as well as coding and medical diagnosis networks. The results show that the BBMB scheme overcomes the memory explosion of bucket-elimination and is applicable for a large range of problems because of its gradual tradeoff of space for time and of time for accuracy.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.