The following researchers will present advanced tutorials at LION3:
- Jean-Charles Regin, ILOG, France
On Global Constraints
- Youssef Hamadi, Microsoft Research Cambridge, UK
From SAT to Parallel SAT Solving
- Olivier Martin , Université Paris-Sud, France
On Variable Neighborhood Search, Iterated Local Search, and further Metaheuristics
- Lukas Kroc, Ashish Sabharwal, and Bart Selman, Cornell University, USA
Satisfied by Message Passing: Probabilistic Techniques for Combinatorial Problems
On Global Constraints
Jean-Charles Régin, Professor, University of Nice-Sophia Antipolis, Ecole Polytechnique Universitaire. [web]Keywords: Constraint Programming, Operation Research, Flow, Matching, Filtering Algorithms, Soft Constraints.
Prerequisite Knowledge: No prerequisite knowledge
Constraint programming (CP) is a general and powerful method to solve some combinatorial problems. This method has been successfully used to solve a large range of real-life applications (roistering, time-tabling, car manufacturing, scheduling etc...), which can be quite different.
CP is on the borderline of AI and OR. CP inherits from IA the language aspect (that is the easy way to define a problem), the flexibility (that is the fact that problems can be easily modified) and the possibility to benefit from the knowledge of the application domain to improve the resolution of a problem. Operational Research brings to CP a lot of nice and powerful algorithms which gives to CP the computational aspect needed to solve some real world problems.
In this talk we will introduce the general principles of this method. We will show its strength and its weakness. Notably, we will insist on one major strength of CP: the Global Constraints. We will see how Global Constraints can be designed and we will give some general guidelines to create new Global Constraints. We will also detail how some OR algorithms are used within Global Constraints and we will present how it leads to new research areas. Some computational results will be given.
Jean-Charles Régin received in 1995 a Ph.D. in Computer Science from the University of Montpellier II (France) and a "Habilitation à Diriger des Recherches" in 2004 at the University of Nice-Sophia Antipolis. He joined ILOG in 1995 as a developer of the ILOG Solver product, was promoted to Ilog Solver manager two years later, becoming the Director of Constraint Programming at Ilog in 2001. He left the company in October 2008 and he is now Professor at the University of Nice-Sophia Antipolis.
Régin is a pioneer of the research on global constraints, currently one of the most active fields of Constraint Programming (CP). Most notably, he has proposed the famous filtering algorithm of the alldiff constraint in one of the most cited papers in CP (with more than 450 references on Google Scholar) also widely known in the Artificial Intelligence and Operations Research communities. He is the author of several global constraints, and has also contributed to the improvement of the classical arc-consistency algorithm and the study of over-constrained problems for which he introduced the concept of soft global constraints. He has designed new CP methods for solving complex combinatorial applications such as sports scheduling, car sequencing, network design and maximum-clique problems. He has published more than 50 papers while working at the industry.
Régin has taught at the most prestigious French engineering schools (Ecole Polytechnique and Ecole Centrale in Paris). In 2005 he spent a sabbatical year at Cornell University. He was the Chair of the CPAIOR conference in 2004, and is the co-editor, with Pascal Van Hentenryck, of the Constraint Programming Letters.
From SAT to Parallel SAT Solving [pdf]
Youssef Hamadi, Microsoft Research Cambridge, UK [web]Keywords: Propositional Satisfiability, parallel search, parallel relaxation.
Prerequisite Knowledge: none.
This tutorial provides a full overview of the most combination of low level techniques used today to tackle industrial instances of the propositional satisfiability problem. It presents the practical and theoretical importance of this problem, and details the common architecture used by modern sequential solvers. From that starting point it presents and discusses several solutions to effectively parallelize sequential solvers. Finally, it details the ManySAT architecture, winners of the parallel track of the 2008 SAT-Race.
Youssef Hamadi holds a Ph.D. in Computer Science from the University of Montpellier II, France. In 2000, he spent one year in the central laboratory of Thales, working on online planning problems and architectures. In 2001, he joined HP-labs to work on agent negotiation and resource optimizing in internet data centers. Since 2003, he is the founding leader of the Constraint Reasoning Group in Microsoft Research Cambridge (MSRC), and since 2007, the co-leader of the Adaptive Combinatorial Search for e-Science project in the MSR/INRIA joint-lab. His research interests include combinatorial optimization in alternative frameworks: parallel, distributed and reconfigurable architectures. He is also interested in the application of machine learning to search. His current focus is on Autonomous Search, parallel satisfiability, automated planning, and knowledge representation.
On Variable Neighborhood Search, Iterated Local Search, and further Metaheuristics [pdf]
Olivier Martin, Université Paris-Sud, France [web]Keywords:Local search, metaheuristics, iterative improvement, global optimization.
Prerequisite Knowledge: none.
Local Search is one of the oldest and simplest algorithms for heuristic optimization. By itself, it is no longer competitive, but many modern metaheuristic rely on it as an internal engine. In this tutorial we review how enlarged neighborhoods and appropriately motivated operators can build on local search to reach state of the art algorithmic performance on numerous complex optimization problems.
O. Martin holds a Ph.D. in theoretical physics from the California Institute of Technology. Much of his research concerns the interface between statistical physics and optimization, with a particular focus on the TSP and MAX-CUT. He was one of the originators of Iterated Local Search and his more recent interests lie in multi-scale approaches. Beyond optimization, he also works on algorithms for importance sampling and stochastic enumeration.
Satisfied by Message Passing: Probabilistic Techniques for Combinatorial Problems [ppt]Keywords:SAT solvers, belief propagation, survey propagation, solution clusters, counting
Prerequisite Knowledge: No prior knowledge of message passing algorithms or SAT solver techniques will be assumed.
The goal of this tutorial is to discuss the basics of and the state of the art in applying message passing techniques to reason about difficult combinatorial problems. This is a promising and relatively new area at the intersection of combinatorial and probabilistic reasoning. Some of these integration attempts, specifically the Survey Propagation (SP) algorithm for random SAT and graph coloring problems, have been astonishingly successful, and have also shed light into the intricate solution space structure of such problems. Message passing algorithms such as Belief Propagation (BP) are widely used for probabilistic inference in graphical models arising in rather diverse fields such as computer vision, information theory, and statistical mechanics. Recently, the application of BP has also been explored for solving hard instances of constraint satisfaction problems. Direct application of BP, unfortunately, runs into issues of convergence and accuracy, in particular when solutions are spatially organized in a large number of "clusters" comprised of "similar" solutions. New techniques, such as Survey Propagation, have therefore been introduced to overcome this clustering barrier.
This tutorial, after covering the necessary background in combinatorial search and message passing algorithms, will introduce a framework of reasoning about solution clusters within which the original SP algorithm for SAT can be derived as an instance of BP, and new algorithms developed for approximately counting solution clusters in other CSPs. The tutorial will also discuss a successful use of message passing algorithms for estimating solution counts of hard, structured combinatorial problems.
Lukas Kroc is a Ph.D. student in computer science at Cornell University, under the supervision of Professor Bart Selman. His research interests lie in the field of artificial intelligence, especially using techniques from probabilistic reasoning to solve combinatorial problems, such as SAT or model counting.
Ashish Sabharwal is a Research Associate in Computer Science at Cornell University, and works at the Intelligent Information Systems Institute and the Institute for Computational Sustainability. He received his M.S. and Ph.D. from the University of Washington, Seattle in 2005, and was a Postdoctoral Associate at Cornell till 2008. His research interests include combinatorial methods, probabilistic inference, multi-agent reasoning, connections to statistical physics, game theory, algorithm design, and complexity. He has (co-)authored over 30 publications and surveys, including two Best Paper Awards, one runner-up prize, and four best paper nominations.
Bart Selman is a Professor of Computer Science at Cornell University. His research interests include efficient reasoning procedures, planning, knowledge representation, and connections between computer science and statistical physics. He has (co-)authored over 100 publications, including six best paper awards. His papers have appeared in venues spanning Nature, Science, Proc. Natl. Acad. of Sci., and a variety of conferences and journals in AI and Computer Science. He has received the Cornell Stephen Miles Excellence in Teaching Award, the Cornell Outstanding Educator Award, an NSF Career Award, and an Alfred P. Sloan Research Fellowship. He is a Fellow of the American Association for Artificial Intelligence and a Fellow of the American Association for the Advancement of Science.