Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

22 March 2001, Computational Logic Seminar, Rosella Gennari

22 March 2001, Computational Logic Seminar, Rosella Gennari
Speaker: Rosella Gennari
Title: Soft Constraint Frameworks
Date and Time: Thursday March 22, 2001, 16:00
Location: Room P.327, ILLC, Plantage Muidergracht 24, Amsterdam

Abstract:
Due to their 2-valued semantics, in some real-life situations, hard constraints may not be sufficient to model a problem:

  • information is incomplete, undetermined or uncertain, in that we can only set a preference on values up to a certain degree of knowledege/ignorance;
  • there exist no solutions to the problem, because the whole hard constraint set is inconsistent;
  • the problem is too difficult to solve, yet we need to find an instantiation for all variables that satisfies the given constraints, ``as many/much as possible''; in particular, that happens whenever there are fixed resource bounds.

Hence, ``soft'' constraints come to be handy: loosely speaking, given a domain variable, a soft constraint is just like a hard one except that the former can assign, to each domain tuple, a ``preference'' or ``uncertainty'' degree further than 0 or 1. Fuzzy and semiring-based constraints are examples of soft constraints.

Different authors have cooked up their own frameworks to define and compute with soft constraints. The best known is the semiring-based framework, by Bistarelli et al., Journal of ACM '97 - a semiring is just a universal algebra with two binary functions and two constants. In their seminal paper, Bistarelli et al. claim that all existing soft constraint frameworks can be translated into their semiring-based one; above all, partial and fuzzy constraint frameworks. Unfortunately, the semiring that they use to translate fuzzy and partial constraints is not the correct one; a simple example explains what goes wrong and why.

Lately, I've been working on a general framework for soft constraints and, above all, on a translation between constraint frameworks for `preserving solution sets'.

For more information, see http://www.illc.uva.nl/~mdr/ACLG/Local/seminar01-1.html.

Please note that this newsitem has been archived, and may contain outdated information or links.