AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 7

Beyond Static Mini-Bucket: Towards Integrating with Iterative Cost-Shifting Based Dynamic Heuristics

Authors

William Lam,Kalev Kask,Rina Dechter,Alexander Ihler

University of California, Irvine,University of California, Irvine,University of California, Irvine,University of California, Irvine


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 7

Volume

Issue:

Vol. 7 No. 1 (2014): Seventh Annual Symposium on Combinatorial Search

Track:

Full Papers

Downloads:

Download PDF

Abstract:

We explore the use of iterative cost-shifting as a dynamic heuristic generator for solving MPE in graphical models via Branch and Bound. When mini-bucket elimination is limited by its memory budget, it may not provide good heuristics. This can happen often when the graphical model has a very high induced width with large variable domain sizes. In addition, we explore a hybrid setup where both MBE and the iterative cost-shifting bound are used in a combined heuristic. We compare these approaches with the most advanced statically generated heuristics.

DOI:

10.1609/socs.v5i1.18316


SOCS

Vol. 7 No. 1 (2014): Seventh Annual Symposium on Combinatorial Search