AND/OR Branch-and-Bound for Graphical Models

Abstract

The paper presents and evaluates the power of a new framework for optimization in graphical models, based on AND/OR search spaces. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation. We develop our work on Constraint Optimization Problems (COP) and introduce a new generation of depth-first Branch-and-Bound algorithms that explore an AND/OR search space and use static and dynamic mini-bucket heuristics to guide the search. We focus on two optimization problems, solvingWeighted CSPs (WCSP) and finding theMost Probable Explanation (MPE) in belief networks. We show that the new AND/OR approach improves considerably over the classic OR space, on a variety of benchmarks including random and real-world problems. We also demonstrate the impact of different lower bounding heuristics on Branch-and-Bound exploring AND/OR spaces.