Heuristique de révision et contraintes hétérogènes - 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

Heuristique de révision et contraintes hétérogènes

Résumé

Most constraint solvers use the general AC-5 scheme to handle constraint propagation [24]. AC-5 generalizes the concept of constraint revision. Each constraint type can thus be shipped with its own revision algorithm, with various complexities and performances. Previous papers showed that the order in which constraints are revised have a non-negligible impact on performances of propagation [27, 8, 22, 1]. However, most of the ideas presented on these papers are based on the use of homogeneous propagators for binary constraints defined in extension. This paper give ideas to handle heterogeneous constraints in a general revision schedule.
La plupart des solveurs de contraintes utilisent une méthode de propagation basée sur l'algorithme générique AC-5 [24]. Le principe d'AC-5 est d'abstraire la notion de révision de contrainte. Chaque contrainte dispose d'un propagateur, doté d'un algorithme de propagation spécifique, de complexité et performance variables. Plusieurs travaux ont, par le passé, montré que l'ordre dans lequel les contraintes sont révisées ont un impact non négligeable sur les performances de la propagation [27, 8, 22, 1]. Cependant, la plupart de ces articles se basent sur l'utilisation de propagateurs homogènes, en particulier pour des contraintes binaires définies en extension. Cet article présente différentes idées et techniques permettant un ordonnancement fin des contraintes au sein d'un système de propagation.
Fichier principal
Vignette du fichier
paper_7.pdf (477.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00830360 , version 1 (04-06-2013)

Identifiants

  • HAL Id : hal-00830360 , version 1

Citer

Julien Vion. Heuristique de révision et contraintes hétérogènes. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. ⟨hal-00830360⟩
51 Consultations
193 Téléchargements

Partager

Gmail Facebook X LinkedIn More