Skip to Main content Skip to Navigation
Conference papers

Vers une exploitation dynamique de la décomposition pour les CSPs pondérés

Résumé : Pour résoudre les problèmes de satisfaction de contraintes pondérés, les méthodes basées sur une dé-composition arborescente constituent une approche inté-ressante selon la nature des instances considérées. Sou-vent, les décompositions exploitées visent à réduire la taille maximale des clusters, connue comme étant la lar-geur de la décomposition. En effet, l'intérêt de ce pa-ramètre est lié à son importance par rapport à la com-plexité théorique de telles méthodes. À ce niveau, Min-Fill constitue l'heuristique de référence pour le calcul de décompositions. Cependant, son intérêt pratique pour la résolution de problèmes demeure limité au vu de ses multiples défauts, notamment au niveau de la restriction de la liberté de l'heuristique de choix de variables. Ainsi, nous proposons, dans un premier temps, d'ex-ploiter de nouvelles décompositions pour le problème d'optimisation sous contraintes. Le but de ces décom-positions est de capturer des critères permettant d'aug-menter l'efficacité de la résolution. Dans un second temps, nous proposons d'exploiter ces décompositions plus dynamiquement dans le sens où la résolution d'un sous-problème ne se baserait sur la décomposition que lorsque cela semble utile. Les expérimentations réalisées montrent l'intérêt pratique des nouvelles décompositions ainsi que l'apport de leur exploitation dynamique. Abstract When solving weighted constraint satisfaction problems , methods based on a tree-decomposition constitute an interesting approach depending on the nature of the considered instances. The exploited decomposi-tions 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 restriction imposed on the freedom of the variable ordering heuristic.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-01785202
Contributor : Philippe Jégou <>
Submitted on : Monday, May 7, 2018 - 11:28:47 AM
Last modification on : Monday, March 30, 2020 - 8:44:56 AM
Long-term archiving on: : Monday, September 24, 2018 - 6:07:31 PM

File

JFPC-2017-Jegou-2.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01785202, version 1

Citation

Philippe Jégou, Hanan Kanso, Cyril Terrioux. Vers une exploitation dynamique de la décomposition pour les CSPs pondérés. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785202⟩

Share

Metrics

Record views

106

Files downloads

61