Skip to Main content Skip to Navigation
Conference papers

Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP

Résumé : L'´ etude des triangles cassés devient de plus en plus ambitieuse, par la résolution desprobì emes de satisfaction de contraintes (CSP) en temps polynomial d'un coté, et par la réduction de l'espace de recherchè a tra-vers l'´ elimination de variables et la fusion de valeurs de l'autre. Pour cela, plusieurs extensions de ce concept ontétéétudiées ontétéontétéétudiées dans le passé récent, tel que les triangles cassés duaux et les triangles légèrement cassés. Ces extensions ontétéontété introduites dans le but de maximiser soit le nombre de valeurs fusionnées et/ou le nombre d'ins-tances traitables capturées. Mais, aucune d'entre elles n'a préservé toutes les caractéristiques de BTP. Ici, nous introduisons une nouvelle version légère de BTP, que nous appelons m-fBTP (pour flexible broken-triangle property). m-fBTP permet la fusion de valeurs, l'´ elimination de variables et définit une plus grande classe polynomiale pour laquelle la cohérence d'arc est une pro-cédure de décision. Une version plus détaillée en langue anglaise a ´ eté publiéè a AAAI'17 [4].
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-01785215
Contributor : Philippe Jégou <>
Submitted on : Monday, May 7, 2018 - 11:29:48 AM
Last modification on : Monday, March 30, 2020 - 8:42:15 AM
Long-term archiving on: : Monday, September 24, 2018 - 10:34:27 PM

File

JFPC-2017-ElMouelhi-1.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01785215, version 1

Citation

Achref Mouelhi. Une famille de règles d'élimination de variables pour les CSP binaires basées sur BTP. Treizièmes Francophones de Programmation par Contraintes, JFPC 2017, Jun 2017, Montreuil-sur-Mer, France. ⟨hal-01785215⟩

Share

Metrics

Record views

89

Files downloads

45