Return to search

Modélisation et résolution en programmation par contraintes de problèmes mixtes continu/discret de satisfaction de contraintes et d'optimisation

Les contraintes sont un moyen générique de représenter les règles qui gouvernent notre monde. Étant donné un ensemble de contraintes, une question centrale est de savoir s'il existe une possibilité de toutes les satisfaire simultanément. Cette problématique est au cœur de la programmation par contraintes, un paradigme puissant pour résoudre efficacement des problèmes qui apparaissent dans de nombreux domaines de l'activité humaine. Initialement dédiée, dans les années 1980, à la résolution de problèmes d'intelligence artificielle à variables entières, c'est dans les années 1990 que la programmation par contraintes a été employée à la résolution de problèmes à variables réelles. Cependant, les problèmes mixtes —utilisant à la fois variables entières et réelles— n'ont été que très peu considérés jusqu'ici par la programmation par contraintes. Dans cette thèse, nous nous plaçons du point de vue de la résolution de problèmes continus. Nous proposons et mettons en oeuvre différentes améliorations de ce cadre de résolution : • Intégration de la notion de recherche rigoureuse d'optimum au cadre classique de résolution sans objectif, afin de modéliser et résoudre un problème de conception en robotique ; • Collaboration de deux solveurs, l'un discret l'autre continu, plus efficace que chacun des outils pour résoudre les problèmes utilisant contraintes continues et contraintes discrètes ; • Comparaison des différentes modélisations et filtrages possibles de la contrainte globale discrète alldifferent, permettant de l'utiliser dans un solveur dédié au continu ; • Spécialisation des techniques de filtrage basées sur l'arithmétique des intervalles, augmentant la puissance de filtrage des contraintes arithmétiques discrètes et mixtes.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00560963
Date07 October 2010
CreatorsBerger, Nicolas
PublisherUniversité de Nantes
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.0023 seconds