ECAI 2000 Tutorial on

Solving and Programming with Soft Constraints: Theory and Implementation

Philippe Codognet and Francesca Rossi

August 21-22, 1999

Berlin, Germany

Summary :
In the last 5-10 years, a lot of effort has been devoted to extending the classical notion of constraint, whose truth value is computed in a boolean (true/false) algebra, to be able to model features like fuzziness, uncertainty, optimization, probability, and partial satisfaction. Soft constraints are meant to satisfy this need, by associating to each tuple, or to each constraint, an element from a set, to be interpreted as a cost, or a level of preference, or a probability, or other.

This tutorial will describe the current state-of-the-art in soft constraints, by reviewing the existing frameworks and pointing out the relations among them. Then, it will focus on one of the most general frameworks for soft constraints and, for such a framework, it will cover its properties and local propagation algorithms. Finally, it will present an existing programming language, called clp(fd,S), where soft constraints can be naturally used and are efficiently implemented.

Target audience :
The target audience for this tutorial is that part of AI researchers which is interested in constraints and wants to be upadted on the latest developments, like soft constraints are. In fact, it seems increasingly obvious that in real life most problms are much better handled by soft constraints rather than by using the classical concept of hard constraints.

What you will get from the tutorial :
After listening to the tutorial, the audience will have gained at least the following:

Outline :
The outline of the tutorial will be the following:

Prerequisite knowledge:
We will review the main notions of both constraint solving and constraint programming that will be useful for the comprehension of the tutorial. However, we will assume some basic knowledge of logic programming. Therefore, basically each AI researcher who knows the main concepts of logic programming and who is interested in learning how to extend constraints with some soft feature will be able to follow the tutorial.

The tutorialists:

Structure of the presentation:
F. Rossi will give the first part of the tutorial (survey of existing systems, theoretical foundations, and propagation algorithms for soft contraints), while P. Codognet will give the second part (languages for soft constraints, implementation details, applications). This combination will assure a good combination of theory and practice in the tutorial. This will provide the audience with a useful balance of notions both on the theoretical and formal side, and also on the implementation and applications.

Francesca Rossi (