CS&E Seminar: Rina Decther, Monday September 19, 2011
Speaker: Rina Dechter, University of California, Irvine
Title: Recent Advances in Solving Combinatorial Optimization Tasks over Graphical Models
Time and Location: Monday, September 19, 2011, at 12:00, Aula 6
Abstract: In this talk I will present state of the art algorithms for solving combinatorial optimization tasks defined over graphical models (Bayesian networks, Markov networks, and constraint networks) and demonstrate their performance on a variety of benchmarks.
Specifically I will present branch and bound and best-first search algorithms which explore the AND/OR search space over graphical models and will demonstrate the gain obtained by exploiting problem’s decomposition (using AND nodes), equivalence (by caching) and irrelevance (via the power of new lower bound heuristics such as mini-buckets). The impact of additional principles such as exploiting determinism via constraint propagation, the use of good initial upper bounds generated via stochastic local search and the variable orderings ideas may be discussed, as time permits.
This is a joint work with Radu Marinescu
Contacts: Domenico Lembo, Massimo Mecella, Giuseppe De Giacomo
Computer Science & Engineering seminar series web page: www.dis.uniroma1.it/~seminf