Valued Constraints: Islands of Tractability
Dave Cohen
Abstract:
========================================================================
In the classical CSP world we have a set of variables and a set
of constraints. Each constraint associates a "relation" with a "scope".
In the valued CSP framework we instead associates a cost function with
each constraint scope. Thus allowing us to consider certain kinds of
optimisation problem. We call any set of cost functions a valued
constraint language.
A classical constraint relation may be seen as a cost function whose only
costs are zero and infinity. As such Valued constraint languages properly
generalise classical constraint languages and so are NP-hard. We are
interested in discovering "islands of tractability". That is, valued
constraint languages which define tractable optimisation problems.
This talk investigates an algebraic property of valued constraint
languages: the multimorphism. We conjecture that the set of
multimorphisms of a valued constraint language will determine its
expressibility and its complexity in much that same way that the set of
polymorphisms do for classical languages.
In this talk we give some background to this theory. We will also
describe examples which give some
justification to our conjecture.