• Calendar

November 22, Tuesday
12:00 – 13:30

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. Current research is in extending the algorithms into distributed/parallel solving, anytime solutions, m-best solutions, and dvanced heuristic generations. Joint work with Radu Marinescu.