ECAI 2000 Tutorial on

Solving and Programming with Soft Constraints: Theory and Implementation

Philippe Codognet and Francesca Rossi

August 21-22, 1999

Berlin, Germany

www.math.unipd.it/~frossi/ecai2000-tut.html

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:

• a reasonably good idea of the various efforts to produce new formalisms for various classes of soft constraints,
• a deep understanding of the formal tools and properties of one of the most general formalisms for soft constraints,
• enough knowledge to program with soft constraints within the clp(fd,s) language;
• knowledge of the main implementation issues for this language, which could be re-used in other constraint-based languages to add soft constraints to them.

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

• The concept of soft constraint, and its instances
• Survey of existing framworks for soft constraints:
  • Partial constraint satisfaction
  • Fuzzy constraint satisfaction
  • Hierarchical constraint logic programming
  • Valued constraint systems
  • Semiring-based constraint systems
• Semiring-based constraint systems:
  • The formalism
  • Its properties
  • The concept of constraint propagation and related theorems
  • Instances and examples
• the language clp(fd,s):
  • Syntax
  • Semantics
  • Programming methodology
  • Partial arc-consistency
  • Implementation issues
• Application examples :
  • Fuzzy reasoning
  • Diagnosis
  • Time-tabling with preferences

The tutorialists:

• Francesca Rossi
  Universita' di Padova
  Dipartimento di Matematica Pura ed Applicata
  Via Belzoni 7
  35131 Padova, Italy
  E-mail: frossi@math.unipd.it
• Philippe Codognet
  University of Paris 6
  LIP6, case 169
  8, rue du Capitaine Scott
  75015 Paris, FRANCE
  E-mail: philippe.codognet@lip6.fr

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.