Virtual arc consistency for weighted CSP - 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 : 2008

Virtual arc consistency for weighted CSP

Résumé

Optimizing a combination of local cost functions on discrete variables is a central problem in many formalisms such as in probabilistic networks, maximum satisfiability, weighted CSP or factor graphs. Recent results have shown that maintaining a form of local consistency in a Branch and Bound search provides bounds that are strong enough to solve many practical instances. In this paper, we introduce Virtual Arc Consistency (VAC) which iteratively identifies and applies sequences of cost propagation over rational costs that are guaranteed to transform a WCSP in another WCSP with an improved constant cost. Although not as strong as Optimal Soft Arc Consistency, VAC is faster and powerful enough to solve submodular problems. Maintaining VAC inside branch and bound leads to important improvements in efficiency on large difficult problems and allowed us to close two famous frequency assignment problem instances.
Fichier principal
Vignette du fichier
Virtual arc consistency for weighted CSP_1.pdf (351.97 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02752851 , version 1
  • PRODINRA : 186572

Citer

Martin Cooper, Simon de Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki. Virtual arc consistency for weighted CSP. Twenty-third AAAI Conference on Artificial Intelligence, Jul 2008, Chicago, United States. pp.6. ⟨hal-02752851⟩
20 Consultations
13 Téléchargements

Partager

Gmail Facebook X LinkedIn More