Propagation de contraintes arithmétiques

Résumé : Nous nous intéressons à la résolution de problèmes de grandes tailles contenant principalement des contraintes arithmétiques comme des problèmes de plus court chemin. Nous montrons qu'un simple modèle PPC n'est pas compétitif avec des algorithmes ou contraintes spécialisés. Ce phénomène est causé par le mécanisme de propagation de contraintes qui détermine l'ordre dans lequel les contraintes sont révisées. Fort de cette observation, nous proposons de modifier la propagation pour intégrer certaines idées cruciales, mais simples, des algorithmes spécialisés. Nous montrons l'intérêt de cette idée sur des problèmes de plus court chemin et nous questionnons sa généralisation à travers des expériences sur d'autres problèmes. Nous analysons aussi la dynamique du phénomène de propagation et constatons que le nombre de variables traitées plusieurs fois dans une même phase de propagation est faible.
Type de document :
Communication dans un congrès
JFPC 2012, May 2012, Toulouse, France. 2012


https://hal.inria.fr/hal-00812011
Contributeur : Arnaud Malapert <>
Soumis le : jeudi 11 avril 2013 - 15:17:51
Dernière modification le : jeudi 11 avril 2013 - 15:53:04
Document(s) archivé(s) le : vendredi 12 juillet 2013 - 04:07:02

Fichier

malapert-regin-jfpc-12.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00812011, version 1

Collections

Citation

Arnaud Malapert, Jean-Charles Régin. Propagation de contraintes arithmétiques. JFPC 2012, May 2012, Toulouse, France. 2012. <hal-00812011>

Partager

Métriques

Consultations de
la notice

118

Téléchargements du document

70