Branch and Bound with Mini-Bucket Heuristics
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 426-434.
Abstract
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 ( MP E ) 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.
@inproceedings{ijcai1999p62,
title = {Branch and Bound with Mini-Bucket Heuristics},
author = {Kask, Kalev and Dechter, Rina},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {426--434},
year = {1999},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1999/62},
}
TY - CPAPER TI - Branch and Bound with Mini-Bucket Heuristics AU - Kask, Kalev AU - Dechter, Rina T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 426 EP - 434 UR - https://ijcai.org/proceedings/1999/62 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
