T2. Advances in Search and Inference for Combinatorial Optimisation

Open slides

Presenter

Abstract

Graphical models, including constraint networks, belief networks, Markov random fields and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of optimization tasks, including scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. The relevance of such algorithms to planning is either direct (e.g., scheduling, design) or indirect, via certain translation of finite horizon state-based planning problems into constraint expressions, (for classical planning), or into probabilistic expressions such as probabilistic conformant planning.

Algorithms for processing graphical models 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 talk is to present the algorithmic principles behind the progress that has been made in the past decade in this area in the graphical models communities such as Constraint networks and Probabilistic networks. It will focus on 1. how bounded-inference (e.g., mini-bucket and mini-clustering scheme) can be used to generate lower-bound heuristics for search, be it depth-first branch and Bound, or Best-first. 2. How these heuristics are contrasted and compare with Those based on linear programming and on soft arc-consistency, 3. on the role of caching goods during branch and bound search, and 4. on how problem decomposition can be incorporated into search using AND/OR search spaces. All these enhancement yield a new generation of branch and bound and Best-first algorithms that can trade-off time and space using a few controlling parameters.

Complexity analysis and empirical demonstration of all algorithms will be presented on variety of benchmarks for Max-CSP, for the Most Probable Explanation tasks (MPE) for probabilistic reasoning, for Integer programming and for general constraint optimization tasks. Example benchmarks include Radio-frequency problems (for MAX-CSPs), linkage analysis, combinatorial auctions, and coding networks.