Winning the pascal 2011 map challenge with enhanced and/or branch-and-bound

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 cate-gories, 20 seconds, 20 minutes, and 1 hour. Our baseline is a branch-and-bound algorithm that explores the AND/OR context-minimal 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 con-stitutes one of the most powerful MAP/MPE inference methods to date.