|

R196
Winning the PASCAL 2011 MAP Challenge with Enhanced AND/OR Branch-and-Bound
Lars Otten, Alexander Ihler, Kalev Kask, and Rina Dechter

Abstract
This paper describes our entry for the MAP/MPE track of the PASCAL 2011 Probabilistic Inference Challenge, which placed first in all three time limit categories, 20 seconds, 20 minutes, and 1 hour. Our baseline is a branch-and-bound algorithm that explores the context-minimal AND/OR search graph of a graphical model guided by a mini-bucket heuristic. Augmented with recent advances that convert the algorithm into an anytime scheme, that improve the heuristic power via cost-shifting schemes, and using enhanced variable ordering schemes, it constitutes one of the most powerful MAP/MPE inference methods to date.

[pdf]