Are Your (Valued) Relations Difficult?
Dave Cohen ( Royal Holloway London )
The Constraint Satisfaction Problem (CSP) is concerned with the
feasibility of satisfying a collection of constraints. The CSP paradigm
has proven to be useful in many practical applications ranging from
line drawing interpretation to railway scheduling and machine shop
A natural extension of this framework, called the Valued CSP (VCSP), which
allows optimisation, is now also being investigated. Here we are no
longer just interested in feasibility, but in finding the best
In a CSP instance a set of variables must be assigned values from
some domain. The values allowed for certain (ordered) subsets of the
variables are restricted by constraint relations.
The general CSP is NP-hard. However there has been considerable success
in identifying tractable fragments of the CSP.
In the VCSP
framework, for some ordered subsets of the variables, each possible
tuple is given a (possibly infinite) desirability weighting, or cost.
The goal is to find the most desirable (or least cost) total assignment.
We have replaced constraint relations, which define feasible tuples,
with cost functions, which give desirability values to tuples.
Of course, it is harder to find tractable fragments of the VCSP.
In this talk I will describe the CSP and VCSP problems and introduce
some simple algebraic concepts. I will then show why, when the costs
are rational numbers or
infinite, the complexity of the VCSP fragments obtained by limiting
the cost functions is determined these algebraic properties.
Keywords: Constraints, CSP, Complexity, Optimisation.