Vincent Thornary

 French version 

Ph-D student, MENRT research grant

INRIA Rhône-Alpes
655, avenue de l'Europe
38330 Montbonnot Saint Martin - France


Telephone: (+33/0) 4 76 61 53 74
Fax: (+33/0) 4 76 61 54 08
Office: D213

Research topic

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.


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 gzipped][pdf]

Last modified : April 4th 2000