Cohérence d'arc virtuelle dynamique - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Cohérence d'arc virtuelle dynamique

Résumé

Virtual Arc Consistency (VAC) is a recent local consistency for processing Cost Function Networks (or Weighted Constraint Networks) that exploits a simple but powerful connection with classical Constraint Networks. It has allowed to close hard frequency assignment benchmarks and is capable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of classical Constraint Networks. In this work, we show that Dynamic Arc Consistency algorithms can be suitably injected in the virtual arc consistency iterative algorithm, providing noticeable speedups.
La coherence d'arc virtuelle (VAC) est une coherence recente pour les reseaux de fonctions de cout (ou reseaux de contraintes ponderees). VAC exploite une relation simple mais puissante avec les reseaux de contraintes classiques. VAC a permis de clore des problemes d'affectation de frequences diciles, et est capable de resoudre directement les reseaux de fonctions de cout sous-modulaires. L'algorithme pour etablir VAC est un algorithme iteratif qui resout une sequence de reseaux de contraintes classiques. Dans cet article, nous montrons que les techniques utilisees dans les algorithmes de coherence d'arc dynamique peuvent etre injectees dans l'algorithme iteratif de coherence d'arc virtuelle. Cette integration donne une acceleration importante.
Fichier principal
Vignette du fichier
Coherence d'arc virtuelle dynamique_TS_1.pdf (412.79 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-02749182 , version 1 (03-06-2020)

Identifiants

  • HAL Id : hal-02749182 , version 1
  • PRODINRA : 263528

Citer

Thi Hông Hiêp Nguyên, Christian Bessiere, Thomas Schiex. Cohérence d'arc virtuelle dynamique. JFPC 2013 - Neuvièmes Journées Francophones de Programmation par Contraintes, Association Française pour la Programmation par Contraintes (AFPC). FRA., Jun 2013, Aix-en -Provence, France. ⟨hal-02749182⟩
9 Consultations
4 Téléchargements

Partager

Gmail Facebook X LinkedIn More