Branch and Bound with Mini-Bucket HeuristicsKalev Kask(email@example.com) & Rina Dechter (firstname.lastname@example.org)
The paper describes a branch and bound scheme that uses heuristics generated mechanically by the mini-bucket approximation. This scheme is presented and evaluated for optimization tasks such as finding the Most Probable Explanation (MPE ) in Bayesian networks. The mini-bucket scheme yields monotonic heuristics of varying strengths which cause different amounts of pruning, allowing a controlled tradeoff between preprocessing and search. The resulting Branch and Bound with Mini-Bucket heuristic (BBMB), is evaluated using random networks, probabilistic decoding and medical diagnosis networks. Results show that the BBMB scheme overcomes the memory explosion of bucket-elimination allowing a gradual tradeoff of space for time, and of time for accuracy.