Propagation de contraintes arithmétiques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Propagation de contraintes arithmétiques

Résumé

We consider the resolution by constraint programming of large problems, i.e. involving millions of constraints, which mainly imply arithmetic constraints, like shortest path problems or other related problems. We show that a simple constraint programming model is not competitive with dedicated algorithms (or dedicated constraints). This mainly comes from the propagation mechanism, i.e. the ordering along which the constraints are revised. Thus, we propose a modification of this propagation mechanism integrating the main ideas of the dedicated algorithms. We give some experiments for the shortest path problem and more general problems which confirms the robustness of our approach. Last, we give some results showing that only a few variables are considered more than once during a propagation step.
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.
Fichier principal
Vignette du fichier
malapert-regin-jfpc-12.pdf (136.63 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00812011 , version 1 (11-04-2013)

Identifiants

  • HAL Id : hal-00812011 , version 1

Citer

Arnaud Malapert, Jean-Charles Régin. Propagation de contraintes arithmétiques. JFPC 2012, May 2012, Toulouse, France. ⟨hal-00812011⟩
117 Consultations
112 Téléchargements

Partager

Gmail Facebook X LinkedIn More