16th International Conference on Principles and Practice of Constraint Programming

Abstract: This tutorial will present an overview of parallelism in SAT. It will start with a presentation of classical divide and conquer techniques, discuss their ancient origin and compare them to more recent portfolio-based algorithms. It will then present the impact of clause-sharing on their performances and discuss various strategies used to control the communication overhead. A particular technique used to control the classical diversification/intensification tradeoff will also be presented. Finally, perspectives will be given which will relate the current parallel SAT technologies to the expected evolution of computational platforms, leading to distributed SAT solving scenarios.

Bio: Youssef Hamadi is the founder and leader of the Constraint Reasoning Group in Microsoft Research Cambridge, United Kingdom, the co-founder and co-leader of the Adaptive Combinatorial Search for e-Science project in the MSR-INRIA joint-lab, in Orsay, France. He is also the founder and co-director of the Microsoft-CNRS chair Optimisation for Sustainable Development, at Ecole Polytechnique, Palaiseau, France.

He is interested in the design of complex systems based on multiple formalisms feed by different information channels to plan ahead and perform smart decisions. His work is set at the intersection of Optimization and Artificial Intelligence. Currently, he focuses on Autonomous Search, Parallel Search, and Propositional Satisfiability.

Short abstract: The tutorial will present distributed constraint satisfaction problems (DisCSPs) and optimization problems (DisCOPs) and search algorithms for solving them. Multiple families of complete and local search algorithms, privacy issues of distributed DisCSP search, measures of performance, and distributed heuristics.

Abstract: Distributed search by agents is an important topic of distributed AI. In the last decade a sizable body of work on distributed constrained search has imerged. Traditionally, this field has been named "Ditributed Constraints Satisfaction" (DisCSPs) and "Distributed constraints optimization" (DisCOPs). The tutorial includes three main parts that form its backbone. The first and most important part introcuces in great detail search algorithms for DisCSPs and DisCOPs. The algorithmic part of the exposition will include ordering heuristics. Both asynchronous heuristics and sequential ones.

The second part of the presentation of Distributed Search by Constrained Agents includes a comprehensive study of distributed performance measures for all algorithms. Based on the resulting coherent and asynchronous scale of performance, an extensive experimental evaluation can be constructed including behavior under message delays.

The third part of our presentation relates to the inherent distributed nature of DisCSPs and DisCOPs and addresses potential problems such as the privacy of information used during search.

Detailed outline:

• DisCSP search algorithms - Asynchronous Backtracking; Asynchronous Forward-checking
• DisCOP algorithms - Asynchronous distributed optimization (ADOPT); Asynchronous Forward-Bounding;
• Concurrent Performance measures
• A note on Privacy
• Future directions - Cooperative search by self-interested Agents

Click here for biographies of the speakers

Short description: This tutorial is intended to provide a new synthesis of the Valued Constraint Satisfaction Problem by summarizing some of the key lessons and describing the key features that underlie the considerable progress that has been made by VCSP solvers in the past decade.

Abstract: The Valued Constraint Satisfaction Problem is a general framework to deal with over-constrained CSPs and combinatorial optimization problems. The optimization of the combined cost of local cost functions, central in the Valued CSP framework, captures problems such as Weighted MaxSAT, Weighted CSP, Maximum Probability Explanation (MPE) in Bayesian networks or Maximum A Posteriori Probability (MAP) in Markov random fields. It has applications in many areas including resource allocation and bioinformatics.

The presentation will be focused on (1) defining the notion of valuation structure and giving its main properties, (2) describing tractable language/structural subclasses, presenting the notions of submodularity and tree decomposition, (3) introducing complete search methods which exploit the problem structure, and finally (4) describing problem transformations based on equivalence-preserving operations and soft consistency. This tutorial should be both of theoretical and practical interest to a large part of the CP community. The techniques covered in the tutorial will be exemplified using a variety of applications (e.g., scheduling, resource allocation, diagnosis, and various bioinformatics tasks).

Biographies: Simon de Givry obtained 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 research 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 use at INRA. In collaboration with researchers in Toulouse, Barcelona, Munich, and Hong Kong, he co-managed a collaborative and open-source constraint optimization platform toolbar/toulbar2, the winner of several solver competitions (UAI-10, UAI-08, MAXCSP-08, MAXCSP-06, MAXSAT-06). He has co-organized several international workshops on soft constraints.

Martin Cooper obtained his PhD in Computer Science in 1987 from Sheffield University and has held research and teaching posts in universities in England, Australia and France. Since 1993 he has been a Computer Science professor at the University of Toulouse 3. Although his main research area is constraints and, in particular, soft constraints, he has also written two books on computer vision as well as articles in computational linguistics and planning. He has worked with Thomas Schiex and Simon de Givry on various generalisations of local consistency to optimisation problems. A longstanding collaboration with Peter Jeavons and David Cohen has led to several contributions to the theory of tractable classes of constraint problems.

Peter Jeavons obtained his PhD in Compuer Science in 1990 from the University of London after a brief spell in industrial software development. He worked at Royal Holloway, University of London, with David Cohen, for over 10 years and is now Professor of Computer Science at the University of Oxford. His research interests are in the complexity of constraint satisfaction, and in bioinformatics.

Abstract: Although the term 'backdoor' is a recent addition to the lexicon of constraint programming and satisfiability, the importance of structure in combinatorial problem solving has been recognised and exploited for decades. The exploitation of structure in SAT, coupled with frequent solver competitions, has significantly advanced the reach of systematic SAT solvers. In this tutorial I will present an overview of backdoors in satisfaction problems. I will discuss backdoors as both descriptive as well as predictive phenomena, and show examples of how they can be exploited in practice. Finally I will make connections between the notion of backdoors in satisfaction problems and the field of fixed parameter tractability.

Bio: Barry O'Sullivan is a senior lecturer in constraints at the Department of Computer Science at University College Cork in Ireland. He is the associate director of the Cork Constraint Computation Centre, Science Foundation Ireland principal investigator, president of the Association for Constraint Programming, chairman of the Artificial Intelligence Association of Ireland, coordinator of the European Research Consortium for Informatics and Mathematics (ERCIM) Working Group on Constraints, and a member of the Executive Council of the Management Science Society of Ireland. His research interests include real-world applications of artificial intelligence, constraint programming and optimization technologies. In July he gave an invited talk at AAAI 2010 entitled "Constraint Programming and Artificial Intelligence: Challenges, Applications and Opportunities".