Dynamic Heuristics for Backtrack Search on Tree-Decomposition of CSPs

Philippe Jégou, Samba Ndojh Ndiaye, Cyril Terrioux

This paper deals with methods exploiting tree-decomposition approaches for solving constraint networks. We consider here the practical efficiency of these approaches by defining five classes of variable orders more and more dynamic which preserve the time complexity bound. For that, we define extensions of this theoretical time complexity bound to increase the dynamic aspect of these orders. We define a constant k allowing us to extend the classical bound from O(exp(w+1)) firstly to O(exp(w+k+1)), and finally to O(exp(2(w+k+1)-s^-)), with w the "tree-width" of a CSP and s^- the minimum size of its separators. Finally, we assess the defined theoretical extension of the time complexity bound from a practical viewpoint.