Most automated reasoning problems in artificial intelligence are computationally hard (NP-hard). Therefore the design of approximation algorithms that trade accuracy for efficiency has great practical importance. The focus of this thesis is on the design and analysis of efficient algorithms for graphical models, such as constraint networks and belief networks. Our approach is to combine conditioning (such as backtracking search) with inference (such as variable elimination), where either conditioning, or inference, or both are being approximated. The central idea of this thesis is that efficiency can be gained by taking advantage of structural properties of graphical models.

This thesis presents a new methodology for combining approximated inference with search. Specifically two schemes for automatically generating search heuristics by inference are proposed. The first uses the mini-bucket approximation method for generating a static heuristic function to be used subsequently by the search algorithm. The second explores an extension of inference-based approximations to a wider class of optimization tasks which allow dynamic heuristic generation throughout the search process. Both approaches dramatically improve Branch-and-Bound and Best-First search.

Subsequently, we also explore several ways of improving stochastic local search methods using inference and demonstrate a significant impact on some classes of constraint problems. On probabilistic optimization tasks we showed that approximating inference is generally superior to approximating conditioning, while some hybrid is superior to both.