Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs

Abstract : When solving weighted constraint satisfaction problems , methods based on tree-decompositions constitute an interesting approach depending on the nature of the considered instances. The exploited decompositions often aim to reduce the maximal size of the clusters, which is known as the width of the decomposition. Indeed, the interest of this parameter is related to its importance with respect to the theoretical complexity of these methods. However, its practical interest for the solving of instances remains limited if we consider its multiple drawbacks, notably due to the restrictions imposed on the freedom of the variable ordering heuristic. So, we first propose to exploit new decompositions for solving the constraint optimization problem. These decompositions aim to take into account criteria allowing to increase the solving efficiency. Secondly, we propose to use these decompositions in a more dynamic manner in the sense that the solving of a subprob-lem would be based on the decomposition, totally or locally, only when it seems to be useful. The performed experiments show the practical interest of these new decompositions and the benefit of their dynamic exploitation.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Philippe Jégou Connect in order to contact the contributor
Submitted on : Friday, April 27, 2018 - 11:40:20 AM
Last modification on : Sunday, June 26, 2022 - 5:58:23 AM


Files produced by the author(s)


  • HAL Id : hal-01779631, version 1


Philippe Jégou, Hélène Kanso, Cyril Terrioux. Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs. 2017 International Conference on Tools with Artificial Intelligence (ICTAI 2017), Nov 2017, Boston, MA, United States. ⟨hal-01779631⟩



Record views


Files downloads