Combined Strategies for Decomposition-Based Methods for Solving CSPs
Philippe Jégou, Samba Ndiaye, Cyril Terrioux · 2009
In this paper, we consider theoretical and practicalmethods based on decompositions of constraint networks. We exploit the fact that decomposition-based methods can be used considering two steps. The first step is related to the (hyper)graphical decomposition (e.g. Tree-Decomposition [16] or Hypertree-Decomposition [7]) while the second step exploits the decomposition to solve the CSPs. Thanks to this approach, we define then hybrid methods which can be optimal from a theoretical viewpoint while being efficient in practice. The complexity analysis of these combined methods allows us to give a more detailed presentation of the Constraint Tractability Hierarchy introduced in [7]. Finally, we justify our approach with experimental results.