Cohérence d'arc virtuelle dynamique - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

Cohérence d'arc virtuelle dynamique

Abstract

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 cohérence d'arc virtuelle (VAC) est une cohérence récente pour les réseaux de fonctions de coût (ou réseaux de contraintes pondérées). VAC exploite une relation simple mais puissante avec les réseaux de contraintes classiques. VAC a permis de clore des problèmes d'af-fectation de fréquences difficiles, et est capable de ré-soudre directement les réseaux de fonctions de coût sous-modulaires. L'algorithme pourétablir VAC est un algo-rithme itératif qui résout une séquence de réseaux de contraintes classiques. Dans cet article, nous montrons que les techniques utilisées dans les algorithmes de cohé-rence d'arc dynamique peuventêtre injectées dans l'al-gorithme itératif de cohérence d'arc virtuelle. Cette intégration donne une accélération importante.
Fichier principal
Vignette du fichier
papier_40.pdf (428.87 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00830411 , version 1 (10-10-2019)

Identifiers

  • HAL Id : lirmm-00830411 , version 1

Cite

Thomas Schiex, Christian Bessiere, Thi Hông Hiêp Nguyên. Cohérence d'arc virtuelle dynamique. 9èmes Journées Francophones de Programmation par Contraintes (JFPC 2013), Jun 2013, Aix-en-Provence, France. pp.249-258. ⟨lirmm-00830411⟩
130 View
40 Download

Share

Gmail Facebook X LinkedIn More