Propagation de contraintes arithmétiques - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

Propagation de contraintes arithmétiques

(1, 2) , (1, 2)
1
2

Abstract

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
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

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

Identifiers

  • HAL Id : hal-00812011 , version 1

Cite

Arnaud Malapert, Jean-Charles Régin. Propagation de contraintes arithmétiques. JFPC 2012, May 2012, Toulouse, France. ⟨hal-00812011⟩
112 View
106 Download

Share

Gmail Facebook Twitter LinkedIn More