Set constraint satisfaction problems with optimisation criteria
Constraint Satisfaction Problems (or CSP) are combinatorial problems usually
defined by a set of variables which are subject to a set of constraints
and which take their values in a set of associated domains. When a NP-complete
problem is modelled by a CSP, one may gain in reducing the search space
of a solution by using consistency techniques. Those filtering rules aim
at eliminating from domains those values which cannot be part of any feasible
solution.
The use of set-valued variables (variables whose value is a set of
values) has shown to be an efficient way to represent multiple solutions
of a CSP, by avoiding repetition and precedence considerations. In this
context, we call set CSP, a CSP in which each variable is set-valued, and
can only take a finite set of values of depth one (set of set of values,
for instance, are not allowed).
Because they model a wide variety of problems such as program analysis,
type inference, tree automata, frequency allocation, set constraints are
a growing field of interest.
Publication
V. Thornary, J.
Gensel, A hybrid representation for set constraint satisfaction
problems, Workshop on Set Constraints, Fourth International
Conference on Principles and Practice of Constraint Programming, Pisa,
Italy,
October
26-30, 1998. [postscript]
Last modified : December 4th 1998
