Virtual Arc Consistency for Weighted CSP

Abstract

Optimizing a combination of local cost functions on dis-crete variables is a central problem in many formalisms such as in probabilistic networks, maximum satisfiabil-ity, 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 se-quences 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 power-ful enough to solve submodular problems. Maintaining VAC inside branch and bound leads to important im-provements in efficiency on large difficult problems and allowed us to close two famous frequency assignment problem instances.