Abstract
Weighted Constraint Satisfaction Problems (WCSP) provide a robust framework for optimization in AI, but their efficiency depends on the strength of lower bounds used in Branch and Bound search. This paper presents Virtual Arc Consistency (VAC), a technique that bridges the gap between fast heuristics and slow optimal bounds. By applying classical arc consistency to a boolean abstraction of the WCSP, VAC identifies cost-shifting operations that significantly tighten lower bounds. Experimental results show that VAC is orders of magnitude faster than Linear Programming-based methods while providing comparable bounds, enabling the resolution of long-standing open problems in frequency assignment.
Introduction
Many critical AI tasks, ranging from bioinformatics to resource allocation, are modeled as Weighted Constraint Satisfaction Problems (WCSP). Unlike standard CSPs, which seek any satisfying assignment, WCSPs assign costs to constraint violations, aiming to minimize the total cost. Solvers typically use Branch and Bound search, which relies heavily on "lower bounds" to prune the search space.
The challenge is a classic trade-off: fast heuristics like Existential Directional Arc Consistency (EDAC) are quick but often yield weak bounds, while optimal bounds like Optimal Soft Arc Consistency (OSAC) provide the best possible pruning but are computationally expensive, often involving Linear Programming. Virtual Arc Consistency (VAC) aims to find a "sweet spot" that combines high-quality bounds with high computational efficiency.
Methodology: The VAC Algorithm
The core innovation of VAC is the "Virtual Arc Consistency" property. A WCSP is considered virtually arc consistent if its "boolean abstraction"—a version where zero-cost assignments are allowed and non-zero costs are forbidden—is arc consistent in the classical sense.
The VAC algorithm operates in three distinct phases:
- Phase 1 (Instrumented AC): A standard Arc Consistency algorithm is run on the boolean abstraction. If an inconsistency (wipe-out) is detected, it indicates that no zero-cost solution exists, allowing for a global lower bound increase.
- Phase 2 (Computing $\lambda$): The algorithm traces the history of deletions to determine the maximum cost "quantum" ($\lambda$) that can be shifted from constraints to the global lower bound without resulting in negative costs.
- Phase 3 (Applying EPTs): A sequence of Equivalence Preserving Transformations (EPTs) is applied to redistribute costs and formally increase the lower bound.
This iterative process continues until the boolean abstraction becomes arc consistent or the incremental gains fall below a predefined threshold.
Key Insights
Submodularity and Polynomial Time
A significant theoretical contribution of this work is the proof that VAC can solve submodular WCSPs in polynomial time. Submodularity is a discrete analogue to convexity; VAC is among the few local consistency techniques capable of directly exploiting this property to find global optima efficiently.
Rational Cost Shifting
While many previous "soft" arc consistency methods were restricted to integer cost movements, VAC utilizes rational numbers. This flexibility allows the algorithm to reach tighter lower bounds that are inaccessible to integer-only methods, significantly improving pruning power in complex search trees.
Experimental Results
The authors evaluated VAC against state-of-the-art benchmarks, including Random Max-CSP, submodular problems, the Uncapacitated Warehouse Problem (UWLP), and the Radio Link Frequency Assignment Problem (RLFAP).
- Closing Open Problems: VAC successfully closed two RLFAP instances (
graph11andgraph13) that had remained unsolved for over a decade. - Speed vs. Strength: Compared to the optimal OSAC, VAC is one to two orders of magnitude faster while maintaining nearly identical lower bound quality.
- Efficiency on Submodular Problems: On submodular problems with 150 variables, VAC reached solutions in approximately 1 second, whereas previous methods like EDAC failed to complete within 10,000 seconds.
Conclusion
Virtual Arc Consistency represents a major advancement in local consistency for WCSPs. By reducing the weighted optimization problem to a sequence of classical boolean CSPs, VAC leverages decades of research in efficient arc consistency algorithms. Its ability to provide near-optimal bounds with high efficiency makes it a powerful tool for solving complex real-world optimization problems. Future work includes integrating Dynamic Arc Consistency to further reduce overhead and extending the framework to non-binary constraints.
Summary updated