Abstract
AND/OR search spaces have recently been introduced as a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. In [MD05a] we introduced a linear space AND/OR Branch-and-Bound (AOBB) search scheme that explores the AND/OR search tree for solving optimization tasks. In this paper we extend the algorithm by equipping it with a context-based adaptive caching scheme similar to good and nogood recording, thus it explores an AND/OR graph rather than the AND/OR tree. We also improve the algorithm by using a new heuristic for generating close to optimal height pseudo-trees, based on a well known recursive decomposition of the hypergraph representation. We illustrate our results using a number of benchmark networks, including the very challenging ones that arise in genetic linkage analysis.