Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Wednesday, June 3, 2020 - 7:02:28 PM
Last modification on : Friday, November 18, 2022 - 4:13:45 AM
Long-term archiving on: : Saturday, December 5, 2020 - 2:45:32 AM


Virtual arc consistency for we...
Publisher files allowed on an open archive


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



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⟩



Record views


Files downloads