Maintaining Virtual Arc Consistency Dynamically during Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

Maintaining Virtual Arc Consistency Dynamically during Search

Abstract

Virtual Arc Consistency (VAC) is a recent local consistency for processing cost function networks (aka weighted constraint networks) that exploits a simple but powerful connection with standard 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 standard constraint networks. This algorithm has been improved by exploiting the idea of dynamic arc consistency between each iteration, leading to the dynamic VAC algorithm. When VAC is maintained during search, the difference between two adjacent nodes in the search tree is also limited. In this paper, we show that the incrementality of Dynamic VAC can also be useful when maintaining VAC during search and we present results showing that maintaining dynamic VAC during search can effectively accelerate search.
Fichier principal
Vignette du fichier
Hiep14.pdf (369.74 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01228369 , version 1 (13-11-2015)

Identifiers

Cite

Simon de Givry, Thomas Schiex, Christian Bessiere, Thi Hông Hiêp Nguyên. Maintaining Virtual Arc Consistency Dynamically during Search. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2014, Limassol, Cyprus. pp.8-15, ⟨10.1109/ICTAI.2014.13⟩. ⟨lirmm-01228369⟩
216 View
261 Download

Altmetric

Share

More