The tutorial will provide participants with a firm understanding of the key features that underlie the considerable progress that has been made in the past decade in solving combinatorial optimization problems over graphical models. We will show that the key to designing powerful algorithms lies in detecting and exploiting useful structural features of the given problem instance. Such features include: 1. decomposability (e.g., breaking a problem into subproblems that can be solved independently), 2. subproblem equivalence (storing previous solutions and reusing them whenever similar subproblems are encountered), 3. subproblem irrelevance (identifying problem subspaces that could be pruned during problem solving search). We will show that recognizing and exploiting these features in a cost-effective manner is essential for advanced constraint optimization techniques. The presentation will be focused on algorithmic methods emphasizing theoretical aspects and applications. The techniques covered in the tutorial will be exemplified on different type of graphical frameworks (weighted constraint networks, probabilistic networks, integer programming) using a variety of applications (e.g., scheduling, diagnosis, bioinformatics tasks and web-based applications).
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, an MS degree in Applied Mathematics from the Weizmann Institute and a BS 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 the author of Constraint Processing published by Morgan Kaufmann, 2003, has authored over 150 research papers, and has served on the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and Logical Method in Computer Science (LMCS). She was awarded the Presidential Young investigator award in 1991, is a Fellow of the Association for the Advancement of Artificial Intelligence since 1994, was a Radcliffe Fellowship 2005-2006 and received the 2007 Association of Constraint Programming (ACP) research excellence award.
Simon de Givry got his PhD in 1998 (Toulouse, France) on simplification and lower bounding techniques for constraint optimization. From 1998 to 2002, he worked in a private research company on hybrid search methods in constraint programming for solving real-time combinatorial applications. He joined Thomas Schiex's bioinformatics team (INRA, Toulouse) in 2002. His main topic of interest is the application of soft constraint techniques to new domains, and in particular in bioinformatics. His recent publications concern new lower bounds for constraint optimization and their combination with an exploitation of the problem graph structure. This work has been applied with success on a large-scale problem in genetics (pedigree analysis), currently in used at INRA. In collaboration with researchers in Toulouse and Barcelona, he co-managed a collaborative and open-source constraint optimization platform toolbar/toulbar2, the winner of several solver competitions (UAI-08, MAXCSP-08, MAXCSP-06, MAXSAT-06). He co-organized two international workshops on soft constraints in 2005 and 2008.
Radu Marinescu is a post-doctoral researcher at the Cork Constraint Computation Centre (4C), University College Cork working with Prof. Eugene Freuder. He received his PhD and MS degrees in Computer Science from the University of California, Irvine (in 2008 and 2004, respectively) under the supervision of Prof. Rina Dechter, and a BS degree in Computer Science from the University ''Politehnica'' of Bucharest. His research centers on search algorithms that explore the AND/OR search spaces, for graphical models, and use the Mini-Bucket approach the generate heuristic functions automatically. During the past years he worked within several optimization frameworks that arise in the areas of constraint based reasoning (constraint networks) and reasoning under uncertainty (belief networks).
Thomas Schiex got his PhD in Computer Science in 1991 (Toulouse, France). After a short period in a software company, he started to work on Constraint Network technology and its application to Planning and scheduling in a French national aerospace agency (ONERA). Motivated by space and telecommunication problems, he developed different learning and local consistency techniques for CSP. Most of his work in Constraint Networks is however organized around the introduction of valued CSP in 1995, a cost function based graphical model oriented towards optimization. This includes dedicated complete optimization algorithms and the extension of "local consistency" to optimization problems, defining strong incremental lower bounds for constraint optimization. In collaboration with S. de Givry and other colleagues, these algorithms have been applied to different problems in scheduling, resource allocation and bioinformatics (such as pedigree analysis or RNA gene localization) but also naturally apply to other graphical models such as Bayes nets, weighted MAXSAT or Markov random fields. He is a member of the executive committee of the international Association for Constraint programming, leads the bioinformatics team at INRA (Toulouse, France), participates regularly to AI and CP conferences program committees and to the editorial board of the JAIR and Constraints journal, he has organized several workshops and conferences.
(back)
