| Titre : | Modélisation et Algorithmes de Résolution de Problèmes Sur-Contraints | | Type de document : | texte imprimé | | Auteurs : | T. PETIT, Auteur | | Année de publication : | 2002 | | Langues : | Français (fre) | | Tags : | PROGRAMMATION PAR CONTRAINTES CSP PROBLEMES-SUR-CONTRAINTS CONTRAINTES MOLLES PROBLEMES D'OPTIMISATION PROGRAMMATION PAR CONTRAINTES CSP PROBLEMES D'OPTIMISATION CONSTRAINT PROGRAMMING CSP OPTIMIZATION PROBLEMS | | Index. décimale : | THE Thèses de doctorat | | Résumé : | Cette thèse présente des outils de modélisation et de résolution de problèmes sur-contraints. D'une part, un nouveau paradigme est proposé. Il offre une expressivité supérieure à l'existant et il permet de modéliser des problèmes sur-contraints à l'aide de systèmes de résolution de CSP classiques. D'autre part, le meilleur algorithme de résolution du problème Max-CSP est généralisé afin de traiter des contraintes non binaires et des applications nécessitant de définir des variables ayant de grands domaines, comme par exemple les problèmes d'ordonnancement. Enfin, la force de la programmation par contraintes étant liée à la puissance des algorithmes de filtrage employés, nous étendons à des contraintes relachées le concept de contrainte globale. Ce principe est illustré par une étude algorithmique et expérimentale de la contrainte "AllDiff" dans sa version relachée.
In this work, we present some new algorithms and a new framework for solving over-constrained problems. The new paradigm we introduce is more expressive than existing ones and it allows to deal with over-constrained problems by using classical constraint solvers. The best existing algorithm for Max-CSP is generalized to non binary constraints and to problems involving huge domains, as scheduling problems. Moreover, constraint programming success was proven to be strongly linked to the efficiency of global filtering algorithms. We extend the concept of "global constraint" to constraints that can be violated. We validate the interest of this concept by a study of the relaxed "AllDiff" constraint. | | Directeur(s) de thèse : | BESSIERE C. | | Co-directeur(s) de thèse : | REGIN J.C. | | Président du jury : | HABIB M. | | Rapporteur(s) : | CODOGNET P.;LARROSA J. | | Examinateur(s) : | PUGET J.F. | | Date de soutenance : | 29/11/2002 |
Modélisation et Algorithmes de Résolution de Problèmes Sur-Contraints [texte imprimé] / T. PETIT, Auteur . - 2002. Langues : Français ( fre) | Tags : | PROGRAMMATION PAR CONTRAINTES CSP PROBLEMES-SUR-CONTRAINTS CONTRAINTES MOLLES PROBLEMES D'OPTIMISATION PROGRAMMATION PAR CONTRAINTES CSP PROBLEMES D'OPTIMISATION CONSTRAINT PROGRAMMING CSP OPTIMIZATION PROBLEMS | | Index. décimale : | THE Thèses de doctorat | | Résumé : | Cette thèse présente des outils de modélisation et de résolution de problèmes sur-contraints. D'une part, un nouveau paradigme est proposé. Il offre une expressivité supérieure à l'existant et il permet de modéliser des problèmes sur-contraints à l'aide de systèmes de résolution de CSP classiques. D'autre part, le meilleur algorithme de résolution du problème Max-CSP est généralisé afin de traiter des contraintes non binaires et des applications nécessitant de définir des variables ayant de grands domaines, comme par exemple les problèmes d'ordonnancement. Enfin, la force de la programmation par contraintes étant liée à la puissance des algorithmes de filtrage employés, nous étendons à des contraintes relachées le concept de contrainte globale. Ce principe est illustré par une étude algorithmique et expérimentale de la contrainte "AllDiff" dans sa version relachée.
In this work, we present some new algorithms and a new framework for solving over-constrained problems. The new paradigm we introduce is more expressive than existing ones and it allows to deal with over-constrained problems by using classical constraint solvers. The best existing algorithm for Max-CSP is generalized to non binary constraints and to problems involving huge domains, as scheduling problems. Moreover, constraint programming success was proven to be strongly linked to the efficiency of global filtering algorithms. We extend the concept of "global constraint" to constraints that can be violated. We validate the interest of this concept by a study of the relaxed "AllDiff" constraint. | | Directeur(s) de thèse : | BESSIERE C. | | Co-directeur(s) de thèse : | REGIN J.C. | | Président du jury : | HABIB M. | | Rapporteur(s) : | CODOGNET P.;LARROSA J. | | Examinateur(s) : | PUGET J.F. | | Date de soutenance : | 29/11/2002 |
|
Affiner la recherche Interroger des sources externesModélisation et Algorithmes de Résolution de Problèmes Sur-Contraints / T. PETIT
