Graphical models are widely used to model complex interactions between variables. A graphical model contains many functions over these variables which have an underlying graph structure and represents an overall joint function composed of these functions. Examples include Bayesian networks, Markov networks, and weighted constraint satisfaction problems. In these, a common query is the optimization query, which is to find a joint configuration of variables that optimizes the objective function defined by the joint function.

One of the best frameworks for these queries is the AND/OR search framework, which casts this optimization problem as a heuristic search problem. AND/OR Branch-and-Bound (AOBB) and AND/OR Best-First (AOBF) search are both algorithms that search the AND/OR search space, which exploits conditional independencies in a problem. The performance of these algorithms are highly dependent on the strength of its heuristics, which is the main focus of this thesis.

We first investigate the well-known technique of look-ahead, commonly used in search applications such as games, adapting it to the optimization task in graphical models. In particular, we analyze the typically used MBE heuristic within the AND/OR search framework, establishing a connection between the ``bucket error'' of MBE and the residual. This connection enables a cost-effective scheme that allows look-ahead to be selectively performed only where it is likely to have a positive impact on the heuristic. An extensive empirical evaluation demonstrates that we are able to improve the power of AND/OR Branch-and-Bound.

Second, in seeking an anytime scheme for providing lower bounds on the optimal solution, we explore the impact of subproblem ordering on AOBF. Our analysis demonstrates that this can significantly impact the performance of AOBF for both exact and anytime solutions. We propose heuristics based on the bucket error of MBE and demonstrate their potential.

Third, to tackle problems where MBE is known to perform poorly on, we explore dynamic heuristics that are computed during search rather than static heuristics which are pre-computed such as with MBE. We adapt the FGLP algorithm, a coordinate-descent method for a linear programming relaxation-based bound on the objective, for use a a heuristic generator for AOBB. Through a re-derived update method and a defined update schedule, we demonstrate the advantage of FGLP heuristics on problems known to be difficult when using MBE.

Additionally, we extend AND/OR Multi-valued Decision Diagrams, a framework for the compact representation of functions in graphical models. We provide a previously missing empirical evaluation of previously introduced methods. We also extend the framework to allow for exact bucket elimination to be implemented using AOMDDs, thus pushing the feasibility of bucket elimination on problems that normally require an infeasible amount of memory.