Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs - Archive ouverte HAL Access content directly
Conference Papers Year :

Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs

(1, 2) , (1, 2) , (1, 2)
1
2

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.
Fichier principal
Vignette du fichier
ictai2017-final.pdf (605.89 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01779631 , version 1 (27-04-2018)

Identifiers

  • HAL Id : hal-01779631 , version 1

Cite

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⟩
102 View
177 Download

Share

Gmail Facebook Twitter LinkedIn More