A Framework for Constraint Satisfaction

P. Roy, A. Liret, F. Pachet

LIP6 1999/001: Rapport de Recherche LIP6 / LIP6 research reports
22 pages - Février/February 1999 - Document en anglais.

PostScript : 629 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Objets et Agents pour Systèmes d'Information et de Simulation

Titre français : Un Framework orienté-objet pour la satisfaction de contraintes
Titre anglais : A Framework for Constraint Satisfaction

Résumé : L'objet de ce rapport est de montrer l'intérêt de l'approche par framework pour construire des environnements efficaces et puissants de programmation par satisfaction de contraintes. La programmation par contraintes est un paradigme de résolution de problèmes combinatoires complexes. L'intégration de ce paradigme avec les objets relève de deux objectifs : d'une part, implémenter efficacement les algorithmes de programmation par contraintes ; d'autre part, énoncer et résoudre des systèmes de contraintes complexes de manière simple et rapide. Les systèmes traditionnels offrant une intégration de ces deux paradigmes, utilisent une approche par langage ; ils sont une extension des langages de programmation existants. Objets et contraintes y sont combinés de plusieurs manières.
Dans ce rapport, nous voulons montrer que l'approche par framework est plus adaptée aux besoins de la satisfaction de contraintes orientée objets, que ne l'est l'approche par langage. Nous proposons pour cela un framework destiné à énoncer et résoudre les systèmes de contraintes qui mettent en jeu des objets. Nous l'illustrons sur des exemples variés.

Abstract : This paper discusses the relevance of the framework approach for building efficient and powerful constraint satisfaction programming environments. Constraint satisfaction programming is a paradigm for solving complex combinatorial problems. Integrating this paradigm with objects addresses two different objectives. On the one hand, objects may be used to implement efficiently constraint satisfaction algorithms. On the other hand, objects can be used to state and solve complex constraint problems more easily, and more
efficiently. Traditional systems offering an integration of the two paradigms use a language-based approach, i.e. are extensions of existing programming languages, which integrate both paradigms in various ways. In this chapter, we argue that the framework approach is more adapted to the requirements of embedded object oriented constraint satisfaction than the language-based approach. We propose such a framework for stating and solving constraint problems involving object, and illustrate it on various examples.

Mots-clés : problème de satisfaction de contraintes (CSP), Programmation par objets, Framework

Key-words : Constraint satisfaction, Object-oriented programming, Frameworks

Publications internes LIP6 1999 / LIP6 research reports 1999

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr