CS Colloq: AND/OR Search Strategies for Combinatorial Optimization in Graphical Models

Title: AND/OR Search Strategies for Combinatorial Optimization in Graphical ModelsSpeaker: Radu Marinescu (UCI)Abstract:
The AND/OR search space for graphical models is a new framework for search that is sensitive to the independencies in the model, often resulting in exponentially reduced complexities. The AND/OR search tree search is in most cases exponentially smaller (and never larger) than the OR search tree. The AND/OR search graph is exponential in the treewidth of the graph, while the OR search graph is exponential in the pathwidth. We introduce a new generation of depth-first Branch-and-Bound as well as best-first AND/OR search algorithms that explore the context minimal AND/OR graph for solving general constraint optimization problems over graphical models. In conjunction with the AND/OR search space we also investigate a class of partitioning-based heuristic functions, based on the Mini-Bucket approximation that was shown to be powerful for optimization problems in the context of OR search spaces. Since variable selection can have a dramatic impact on search performance, we also introduce a class of depth-first AND/OR Branch-and-Bound and best-first AND/OR search algorithms that can accommodate various dynamic variable ordering heuristics. An extensive empirical evaluation showed conclusively that the new AND/OR search approach improves considerably over the traditional OR search, on a variety of probabilistic and deterministic benchmarks. We next apply the AND/OR perspective to decision diagrams. We extend them with AND nodes capturing function structure decomposition, resulting in AND/OR Multi-Valued Decision Diagrams (AOMDDs). The AOMDD is a canonical form that compiles a graphical model and has size bounded exponentially by the treewidth, rather than pathwidth (as is the case for OR decision diagrams). We present an AND/OR search based algorithm for compiling AOMDDs, as representations of the optimal set of solutions of a constraint optimization problem. An extensive experimental evaluation proved the efficiency of the weighted AOMDD data structure.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia