Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP

Simon de Givry, Thomas Schiex, Gérard VerfaillieAAAI 2006

Abstract

Solving Weighted Constraint Satisfaction Problems (WCSPs) is a fundamental challenge in optimization, often hampered by the conflict between structural decomposition and constraint propagation. This paper introduces Lc-BTD+, an algorithm that successfully integrates structural tree decomposition with soft local consistency. By tracking cost movements across cluster boundaries, Lc-BTD+ maintains subproblem independence while benefiting from aggressive pruning. Experimental results demonstrate that Lc-BTD+ achieves state-of-the-art performance, notably solving the difficult SCEN-06 frequency assignment benchmark to optimality.

Introduction

Weighted Constraint Satisfaction Problems (WCSPs) involve finding variable assignments that minimize a total cost function, a task that is inherently NP-hard. Researchers typically employ two distinct strategies: structural approaches and propagation approaches. Structural methods utilize Tree Decomposition to break large problems into smaller, independent clusters connected by separators, providing theoretical complexity bounds. Propagation methods use Soft Local Consistency to shift costs within the network, revealing lower bounds that prune the search space.

Historically, these strategies have been difficult to combine. Local consistency mechanisms "push" costs between variables; if these variables reside in different clusters, the independence required for subproblem recording (memoization) is compromised. Lc-BTD+ addresses this intricacy, allowing for the simultaneous use of both techniques.

A constraint graph (left) and its associated tree decomposition (right), illustrating the partitioning of variables into clusters (C1-C7) connected by separators.

Methodology: The Lc-BTD+ Algorithm

The core innovation of Lc-BTD+ (Local Consistency - Backtrack bounded by Tree Decomposition) lies in its ability to manage cost movements while preserving the benefits of decomposition. Key features include:

  • Cost Movement Tracking: The authors implemented a backtrackable data structure, $\Delta W_i^e(a)$, to monitor costs projected or extended across cluster boundaries. This allows the algorithm to adjust recorded subproblem results dynamically when local consistency shifts costs.
  • Enhanced Upper Bounds: Lc-BTD+ utilizes tighter initial upper bounds derived from the current global solution. While this may occasionally necessitate re-solving a subproblem if the bound proves too restrictive, it facilitates significantly more aggressive pruning in practice.
  • Hybrid Pruning: The algorithm integrates local cuts (subproblem-specific) and global cuts (based on the best known global solution) to minimize node exploration.

Experimental Evaluation

The algorithm was evaluated using two primary datasets:

  1. Randomly Generated Instances: "Clique trees" with controlled tree-width and separator sizes were used to test scaling relative to structural complexity.
  2. Radio Link Frequency Assignment Problem (RLFAP): A real-world benchmark focusing on the notoriously difficult SCEN-06 instance and its subsets (SUB1, SUB4).

Key Results and Discussion

Lc-BTD+ demonstrated superior efficiency and robustness across various problem types. A major breakthrough was achieved on the SCEN-06 instance; the FDAC version of Lc-BTD+ was the only tested algorithm capable of proving optimality within a 10-hour limit, completing the task in approximately 2.8 hours (10,309 seconds).

Comparative performance of various BTD+ algorithms and standard solvers on random instances with n=40 variables.

On the SUB4 sub-instance, Lc-BTD+ outperformed traditional BTD by orders of magnitude, finishing in 929 seconds compared to over 122,000 seconds reported in previous studies. The results indicate that stronger local consistencies, such as FDAC, are particularly effective when paired with tree decomposition, especially as separators grow larger.

Conclusion

Lc-BTD+ represents a significant advancement in WCSP solving by reconciling structural decomposition with local consistency. While the recording mechanism remains sensitive to separator size and memory limits, the practical speedups are substantial. Future work may explore the application of this hybrid approach to non-binary constraints, Max-SAT, and Bayesian Networks, as well as the optimization of initial tree decomposition heuristics.

Summary updated

BibTeX
@inproceedings{givry2006exploiting,
  author = {Simon de Givry and Thomas Schiex and Gérard Verfaillie},
  title = {{Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure