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

Authors

  • William Lam University of California, Irvine
  • Kalev Kask University of California, Irvine
  • Rina Dechter University of California, Irvine
  • Alexander Ihler University of California, Irvine

DOI:

https://doi.org/10.1609/socs.v5i1.18316

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.

Downloads

Published

2021-09-01