This thesis presents a new generation of search algorithms for solving combinatorial optimization problems over graphical models. The new algorithms exploit the principles of problem decomposition using the AND/OR search spaces, avoid redundant solution of subproblems using memory, focus on relevant promising portions of the solution space using the power of the mini-bucket heuristics and prune irrelevant spaces using constraint propagation. As we show throughout the chapters of this thesis, putting all these principles together yields powerful algorithms whose performance improves upon earlier schemes significantly, sometimes by several orders of magnitude. We demonstrate the applicability and the generality of our algorithms on optimization tasks over both probabilistic and deterministic graphical models, often showing superior performance on real application such as linkage analysis and circuit design and diagnosis. The following paragraphs elaborate.

Our algorithms explore the AND/OR search spaces of the underlying graphical model. The AND/OR search space is a unifying paradigm for advanced search schemes for graphical models exploiting problem decomposability, which can translate into exponential time savings for search algorithms. In conjunction with the AND/OR search space we also investigate a class of partition-based heuristic functions, based on the Mini-Bucket approximation.

We start by introducing depth-first Branch-and-Bound search algorithms that explore the AND/OR tree, use a variety of sources for heuristic guidance and incorporate some dynamic variable ordering heuristics. We then extend the depth-first AND/OR Branch-and-Bound and best-first search algorithms with the ability to recognize identical subproblems and avoid redundant solutions by caching (similar to good and no-good recording), thus traversing the AND/OR search graph. We also extend all the principles acquired within the general framework of depth-first and best-first schemes to the well known 0-1 Integer Linear Programs.

Our empirical evaluation shows conclusively that the new AND/OR search algorithms improve dramatically over current state-of-the-art approaches exploring the traditional OR search space, in many cases by several orders of magnitude. We illustrate one by one the gain obtained by exploiting problem's decomposition (using AND modes), equivalence (by caching), branching strategy (via dynamic variable ordering heuristics), control strategy (depth-first or best-first) as well as the impact of the lower bound heuristic strength. As well, we investigate the impact of exploiting hard constraint (i.e., determinism) in the problem, the initial upper bound provided to the algorithm, and the quality of the guiding variable orderings.

In the last part of the thesis we also show how our AND/OR search algorithms can be used as compilation algorithms for AND/OR decision diagrams. We present a new algorithm for compiling AND/OR Multi-Valued Decision Diagrams (AOMDDs) that represent the set of optimal solutions. We extend earlier work on AND/OR decision diagrams by considering general weighted graphical models based on cost functions rather than constraints. On various domains we show that we sometimes get a substantial reduction beyond the initial trace of state-of-the-art search algorithms.

Finally, the starting chapter of this thesis (Chapter \ref{ch2}) sets the stage for this whole work by comparing the power of static and dynamic mini-bucket heuristics over regular search spaces and compares against a number of popular stochastic local search algorithms, as well as against the class of iterative belief propagation algorithms.