Virtual arc consistency for weighted CSP - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2008

Virtual arc consistency for weighted CSP

Abstract

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
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

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

Identifiers

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

Cite

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⟩
23 View
17 Download

Share

Gmail Facebook X LinkedIn More