Advances in Search, Inference and Hybrids for Solving Combinatorial Optimization Tasks Rina Dechter University of California at Irvine Algorithms for constraint optimization are of two primary types: inference-based and search-based. Inference-based algorithms (e.g., variable-elimination, join-tree clustering) are time and space exponentially bounded by the tree-width of the problem's graph. Search-based algorithms (e.g., branch and bound) can be executed in linear space and often outperform their worst-case predictions. The thrust of advanced schemes is in combining inference and search yielding a spectrum of memory-sensitive algorithms applicable to numerous optimization tasks across variety of graph-based knowledge bases such as constraint optimization, Bayesian networks and Markov decision processes. The goal of this tutorial is to present the algorithmic principles behind the progress that has been made in the past decade in this area in the constraint processing community. It will focus on 1) how bounded-inference (e.g., mini-bucket and mini-clustering schemes) can be used to generate lower-bound heuristics for branch and bound search, 2) on the role of caching goods during branch and bound search, and 3) on how problem decomposition can be incorporated into search using AND/OR search spaces. All these enhancements yield a new generation of branch and bound algorithms that can trade-off time and space using a few controlling parameters. The tutorial will also discuss cycle-cutset and w-cutset, as well as super-bucket elimination approaches, which are orthogonal to the above mentioned branch and bound schemes and therefore allow additional level of integration of all the involved principles. Complexity analysis and empirical demonstration of all algorithms will be presented on variety of benchmarks for Max-CSP and for the MPE task for probabilistic reasoning. Example benchmarks include radio-frequency problems (for MAX-CSPs) and linkage analysis and coding networks (for MPE.)