ML Anthology

Branch and Bound with Mini-Bucket Heuristics

Kalev Kask, Rina Dechter
IJCAI 1999 pp. 426-435
/ijcai/1999/kask1999ijcai-branch/

Abstract

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. 1

PDF Semantic Scholar

Cite

Text

Kask and Dechter. "Branch and Bound with Mini-Bucket Heuristics." International Joint Conference on Artificial Intelligence, 1999.

Markdown

[Kask and Dechter. "Branch and Bound with Mini-Bucket Heuristics." International Joint Conference on Artificial Intelligence, 1999.](https://mlanthology.org/ijcai/1999/kask1999ijcai-branch/)

BibTeX

@inproceedings{kask1999ijcai-branch,
  title     = {{Branch and Bound with Mini-Bucket Heuristics}},
  author    = {Kask, Kalev and Dechter, Rina},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {1999},
  pages     = {426-435},
  url       = {https://mlanthology.org/ijcai/1999/kask1999ijcai-branch/}
}