La programmation par contraintes est souvent décrite, utopiquement, comme un paradigme déclaratif dans lequel l'utilisateur décrit son problème et le solveur le résout. Bien entendu, la réalité des solveurs de contraintes est plus complexe, et les besoins de personnalisation des techniques de modélisation et de résolution évoluent avec le degré d'expertise des utilisateurs. Cette thèse porte sur l'enrichissement de l'arsenal des techniques disponibles dans les solveurs de contraintes. D'une part, nous étudions la contribution d'un système d'explications à l'exploration de l'espace de recherche, dans le cadre spécifique d'une recherche locale. Deux heuristiques de voisinages génériques exploitant singulièrement les explications sont décrites. La première se base sur la difficulté de réparer une solution partiellement détruite, la seconde repose sur la nature non-optimale de la solution courante. Ces heuristiques mettent à jour la structure interne des problèmes traités pour construire des voisins de bonne qualité pour une recherche à voisinage large. Elles sont complémentaires d'autres heuristiques de voisinages génériques, avec lesquels elles peuvent être combinées efficacement. De plus, nous proposons de rendre le système d'explications paresseux afin d'en minimiser l'empreinte. D'autre part, nous effectuons un état des lieux des savoir-faire relatifs aux moteurs de propagation pour les solveurs de contraintes. Ces données sont exploitées opérationnellement à travers un langage dédié qui permet de personnaliser la propagation au sein d'un solveur, en fournissant des structures d'implémentation et en définissant des points de contrôle dans le solveur. Ce langage offre des concepts de haut niveau permettant à l'utilisateur d'ignorer les détails de mise en œuvre du solveur, tout en conservant un bon niveau de flexibilité et certaines garanties. Il permet l'expression de schémas de propagation spécifiques à la structure interne de chaque problème. La mise en œuvre et les expérimentations ont été effectués dans le solveur de contraintes Choco. Cette thèse a donné lieu à une nouvelle version de l'outil globalement plus efficace et nativement expliqué.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-01060921 |
| Date | 28 February 2014 |
| Creators | Prud'Homme, Charles |
| Publisher | Ecole des Mines de Nantes |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0022 seconds