Recent Advances in Solving Combinatorial Optimization Tasks over Graphical Models

Venerdi' 9 Settembre 2011 - Rina Dechter


Venerdi' 9 Settembre 2011, alle ore 11:00 in aula 1C150, la Prof.ssa Rina Dechter (UC Irvine) terra' un seminario dal titolo "Recent Advances in Solving Combinatorial Optimization Tasks
over Graphical Models".

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 joint work with Radu Marinescu.

-Brief bio
Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, a MS degree in Applied Mathematic from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning. Professor Dechter is an author of “Constraint Processing” published by Morgan Kaufmann, 2003, has authored over 100 research papers, and has served on the editorial boards of: Artificial Intelligence (and is co-editor in chief starting 2011), the Constraint Journal, Journal of Artificial Intelligence Research, Logical Method in Computer Science (LMCS) and Journal of Automated Reasoning. She was awarded the Presidential Young investigator award in 1991, is a fellow of the American association of Artificial Intelligence, she was a Radcliffe fellow 2005-06 and was awarded the “Association of Constraint Programming (ACP) award for research excellence" in 2007.

Rif. int. F. Rossi