Maintaining Virtual Arc Consistency Dynamically during Search

Hiep Nguyen 1 Simon De Givry 2 Thomas Schiex 3 Christian Bessière 4, *
* Auteur correspondant
1 ISPED - Institut de Santé Publique, d'Epidémiologie et de Développement
2 UBIA - Unité de Biométrie et Intelligence Artificielle
3 MIAT INRA - Unité de Mathématiques et Informatique Appliquées de Toulouse
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Keywords : Weighted CSP Cost Function Networks Arc consistency Dynamic arc consistency Virtual arc consistency
Type de document :
Communication dans un congrès
ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2014, Limassol, Cyprus. IEEE, IEEE 26th International Conference on Tools with Artificial Intelligence, pp.8-15, 2014, 〈10.1109/ICTAI.2014.13〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01228369
Contributeur : Joël Quinqueton <>
Soumis le : vendredi 13 novembre 2015 - 08:57:19
Dernière modification le : mardi 18 décembre 2018 - 11:58:19
Document(s) archivé(s) le : vendredi 28 avril 2017 - 04:54:00

Fichier

Hiep14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRA | COCONUT | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

Hiep Nguyen, Simon De Givry, Thomas Schiex, Christian Bessière. Maintaining Virtual Arc Consistency Dynamically during Search. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2014, Limassol, Cyprus. IEEE, IEEE 26th International Conference on Tools with Artificial Intelligence, pp.8-15, 2014, 〈10.1109/ICTAI.2014.13〉. 〈lirmm-01228369〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

325

Téléchargements de fichiers

195

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD