Decomposition and good recording for solving Max-CSPs
Philippe Jégou, Cyril Terrioux · European Conference on Artificial Intelligence · 2004
[22] presents a new method called BTD for solving Valued CSPs and so Max-CSPs. This method based both on enumerative techniques and the tree-decomposition notion provides better theoretical time complexity bounds than classical enumerative methods and aims to benefit of the practical efficiency of enumerative methods thanks to the structural goods which are recorded and exploited during the search. However, [22] does not provide any experimental result and it does not discuss the way of finding an optimal solution from the optimal cost (because BTD only computes the cost of the best assignment). Providing an optimal solution is an important task for a solver, especially when we consider real-world instances. So, in this paper, we first raise these two questions. Then we explain how a solution can be efficiently computed and we provide experimental results which emphasize the practical interest of BTD.