Set Intervals in Constraint Logic Programming: Definition and implementation of a language
Intervalles ensemblistes en programmation logique par contraintes : définition formelle et concrète d'un langage
Résumé
Constraint satisfaction techniques have recently been introduced in logic programming to extend the application domain of logic programming languages. Existing languages, based on these techniques, consider arithmetic constraints applied to variables taking their value in domains of integers. This makes concise and natural modeling as well as an efficient resolution of certain np-complete combinatorial problems of a set-theoretic nature difficult. We propose a solution that consists of extending the notion of integer domain to that of set domain (set of sets). We specify a set domain by an interval whose lower and upper bounds are known sets, ordered by the set-inclusion. We define the formal and concrete structure of a new logic programming language based on constraints on set domains, called conjunto. Conjunto includes the symbols of usual set operations (,, /) interpreted in relational form (s s # 1 = s # 2,) and the inclusion relation (). In addition, it provides a set of constraints called graded constraints (eg Cardinality Function) that associate a set with an arithmetic term. This allows us to deal with optimization problems by applying a cost function to measurable terms, i. e. arithmetic, associated with the ensemblist terms. The resolution of the constraints in conjunto is based on constraint satisfaction techniques by reduction of intervals extended to the treatment of set constraints. Thus, the main contribution of this thesis concerns the definition of transformation rules within a generic algorithm, which infer the local consistency of the constraints of the language by reducing the set intervals. A set of operational research applications and combinatorial mathematics were developed with conjunto, illustrating the strengths of the language in terms
Les techniques de satisfaction de contraintes ont été récemment introduites en programmation logique en vue d’étendre le domaine d'application des langages de programmation en logique. Les langages existants, bases sur ces techniques, considèrent des contraintes arithmétiques appliquées a des variables prenant leur valeur dans des domaines d'entiers. Cela rend difficile une modélisation concise et naturelle ainsi qu'une résolution efficace de certains problèmes combinatoires np-complets, de nature ensembliste. Nous proposons une solution qui consiste à étendre la notion de domaine d'entiers a celle de domaine ensembliste (ensemble d'ensembles). Nous spécifions un domaine ensembliste par un intervalle dont les bornes inférieure et supérieure sont des ensembles connus, ordonnes par l'inclusion ensembliste. Nous définissons la structure formelle et concrète d'un nouveau langage de programmation en logique par contraintes sur domaines ensemblistes, appelé conjunto. Conjunto comprend les symboles d’opérations ensemblistes usuels (,, /) interprétés sous une forme relationnelle (s s#1 = s#2,) et la relation d'inclusion (). De plus il pourvoit un ensemble des contraintes appelées contraintes graduées (ex. Fonction de cardinalité) qui associent a un ensemble un terme arithmétique. Cela nous permet de traiter les problèmes d'optimisation en appliquant une fonction de cout aux termes mesurables, i. e. arithmétiques, associes aux termes ensemblistes. La résolution des contraintes dans conjunto est basée sur des techniques de satisfaction de contraintes par réduction d'intervalles étendues au traitement des contraintes ensemblistes. Ainsi, la contribution principale de cette thèse concerne la définition de règles de transformation au sein d'un algorithme générique, qui infèrent la consistance locale des contraintes du langage en réduisant les intervalles ensemblistes. Un ensemble d'applications de recherche opérationnelle et de mathématiques combinatoires ont été développées avec conjunto, illustrant ainsi les forces du langage en terme de rapport expressivité/efficacité
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...