Branch and Bound with Mini-Bucket Heuristics

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

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.