ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Decomposition and good recording for solving Max-CSPs

Philippe Jegou, Cyril Terrioux

[20] 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 structural goods which are recorded and exploited during the search. However, in [20], the authors do not provide any experimental result and they do 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 compute and we provide experimental results which emphasizes the practical interest of BTD.

Keywords: Constraint Satisfaction, Valued CSP, Tree-decomposition

Citation: Philippe Jegou, Cyril Terrioux: Decomposition and good recording for solving Max-CSPs. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.196-200.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).