Adaptive and Opportunistic Exploitation of Tree-decompositions for Weighted CSPs

Philippe Jégou (1, 2) , Hélène Kanso (1, 2) , Cyril Terrioux (1, 2)

1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
2 COALA - COntraintes, ALgorithmes et Applications

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.

Mots clés: solving; Weighted CSP; decomposition

Domaines: Intelligence artificielle [cs.AI]

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⟩