Invited Talks and Tutorials

Invited Talk - CP 2012 (Quebec City, Canada)
Where are the Interesting Problems?
[ Slides ]
Constraint programming has become an important technology for solving hard combinatorial problems in a diverse range of application domains. It has its roots in artificial intelligence, mathematical programming, operations research, and programming languages. In this talk we will discuss a number of challenging application domains for constraint programming, and the technical challenges that these present to the research community.

Invited Talk - AAAI 2010 (Atlanta, Georgia, USA)
Constraint Programming and AI: Challenges, Applications and Opportunities
[ Slides ]
Constraint programming is a powerful tool for modeling and solving complex optimization problems. It is widely used to support industrial decision-making, as well as being used as a component in various intelligent systems. Constraint programming has its origins in constraint satisfaction and logic programming from the field of artificial intelligence, and mathematical programming from the field of operations research. In this talk I will: identify some of the challenges facing the field; present some exciting applications of constraint programming; and give a view of where opportunities lie for the future from the perspectives of both science and application.

Tutorial - AAAI 2010 (Atlanta, Georgia, USA)
An Introduction to Constraint Programming & Combinatorial Optimisation through Numberjack (with E.Hebrard and E.O'Mahony)
[ Slides ]
Computers play an increasingly important role in helping individuals and industries make decisions. For example they can help individuals make decisions about which products to purchase or industries make decisions about how best to manufacture these products. Constraint programming provides powerful support for decision-making; it is able to search quickly through an enormous space of choices, and infer the implications of those choices. This tutorial will teach attendees how to develop interesting models of combinatorial problems and solve them using constraint programming, satisfiability and mixed integer programming techniques. The tutorial will make use of Numberjack, an open-source Python-based optimisation system developed at the Cork Constraint Computation Centre. As such, this tutorial is ideal for graduate students, industrialists, and advanced researchers interested in knowing how to apply optimisation technology to challenging problems. A number of real-world case-studies from domains such as telecommunications, network security, sensor networks, warehouse location, and computational sustainability will be presented. A feature of this tutorial is that it will be hands-on. Attendees will walk away with the basic skills required to implement their own models using an open-source optimisation system.

Tutorial - IJCAI 2009 (Pasadena, California, USA)
Computing Explanations in Problem Solving (with U.Junker)
[ Slides ]
Generating explanations of the results of problem solving has always been an important objective of artificial intelligence (AI) research, but has been traditionally addressed by specialized techniques. Explanations are critically important in interactive systems such as web-based product configurators, personal assistants, expert systems, and model development tools. Moreover, explanation techniques can improve the quality of results in test generation, software verification, and decomposition methods in combinatorial optimization. This tutorial addresses a broad AI audience and seeks to lay a general foundation for explanation generation, which is valid for a large range of AI problems (product configuration, multi-criteria optimization, constraint satisfaction, satisfiabililty, recommender systems, case-based reasoning, diagnosis, debugging, ontological reasoning, etc.). It exploits the fact that explanations developed for different kinds of problems have a similar form and can be computed with similar means. The tutorial assumes basic knowledge in problem solving and automated reasoning, e.g. constraint satisfaction, when motivating explanation problems. The presentation of the explanation problems themselves and their algorithms is self-contained. The tutorial will be of interest to students and established researchers alike. Given the ubiquity of explanation problems, this tutorial crosses boundaries between many subfields of AI. Industrialists will also find this tutorial useful, since explanation generation is of considerable commercial value in many domains.

Tutorial - CP 2009 (Lisbon, Portugal)
Exploiting Fixed-Parameter Tractability in Satisfiability and Constraint Satisfaction (with I.Razgon)
[ Slides ]
Many problems we attempt to solve using satisfiability or constraint programming techniques are NP-Complete or harder. The field of parameterised complexity provides an orthogonal view to classical complexity theory. It attempts to deal with NP-Hardness by identifying problems whose exponential worst-case behaviour is, in fact, only polynomially dependent on the size of the problem $n$, but exponentially dependent on a parameter $k$, independent of $n$. Ideally we wish to identify fixed-parameter algorithms for solving such problems that rely on parameters that tend to be small in practice. The field of parameterised complexity has many similarities with the areas of satisfiability and constraint solving from both the conceptual point of view as well as through its results. Informally, from the conceptual point of view, there are two broad classes of techniques for the design of fixed-parameter algorithms: reformulation and preprocessing. In this context, reformulation means that the search space is represented in such a way that the number of explored possibilities depends exponentially only on the parameter k but polynomially on the input size n. The methodology of preprocessing aims at designing polynomial-time algorithms for reducing the size of the search space. The methodologies of reformulation and preprocessing in parameterized complexity are very similar to what we understand as reformulation and preprocessing in constraint programming. This similarity opens possibilities for two very intriguing interconnections:

  • The method of parameterized complexity can be regarded as a theoretical foundation for particular kinds of reformulation and preprocessing in constraint programming.
  • Researchers in the area of constraint programming can apply their training and experience in reformulation and preprocessing in order to solve hard open problems in the area of parameterized complexity; this is, in fact, what has happened in our case.
In this tutorial we will: provide an overview of the field; survey the work that has been done in the area of parameterised complexity for satisfiability and constraint solving; and present an in-depth analysis of one challenging open problem that was recently resolved by the tutorialists that is of interest in satisfiability and constraint optimization.

Invited Talk - ASPL 2008 (Limerick, Ireland)
Challenges in Constraint-based Configuration and Explanation
First Workshop on Analyses of Software Product Lines Limerick, Ireland, Sept. 2008

Tutorial - ACP Summer School 2008 (St.Andrews, Scotland)
Explanations in Constraint Programming
Association for Constraint Programming Summer School St. Andrews University, Scotland 30th June 4th July 2008

Tutorial - ACP Summer School 2008 (St.Andrews, Scotland)
Modelling and Solving Two Complex Problems using CP and OR
Association for Constraint Programming Summer School St. Andrews University, Scotland 30th June 4th July 2008

Tutorial - ACP Summer School 2008 (St.Andrews, Scotland)
Some Classic Papers in Constraint Modeling and Solving
Association for Constraint Programming Summer School St. Andrews University, Scotland 30th June 4th July 2008

Invited Talk - CSCLP 2006 (Lisbon, Portugal)
Constraints and Learning
CSCLP 2006: Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming Lisbon, 26th June 2006