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 metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-01779631
Contributor : Philippe Jégou <>
Submitted on : Friday, April 27, 2018 - 11:40:20 AM
Last modification on : Sunday, June 23, 2019 - 5:54:02 PM

File

ictai2017-final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01779631, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

111

Files downloads

104