Une heuristique basée sur l'historique des conflits pour les problèmes de satisfaction de contraintes

Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Résumé : L’heuristique de choix de variables est une brique importante pour les algorithmes de résolution du problème de satisfaction de contraintes (CSP). Elle a une influence souvent considérable sur l’efficacité de la recherche et permet, d’une certaine manière, d’exploiter la structure des instances. Dans cet article, nous proposons l’heuristique CHS (pour Conflict-History Search) qui est une heuristique dynamique et adaptative pour la résolution d’instances CSP. Elle repose sur les échecs rencontrés durant la recherche et considère leur temporalité tout au long de la résolution. Une technique d’apprentissage par renforcement est exploitée pour estimer l’évolution de la difficulté des contraintes durant la recherche. Les expérimentations réalisées sur des instances au format XCSP3 permettent de montrer que l’intégration de CHS au sein d’un solveur basé sur l’algorithme MAC s’avère pertinente, conduisant notamment à des résultats meilleurs que ceux obtenus avec des heuristiques de l’état de l’art comme dom/wdeg et ABS.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02162856
Contributor : Cyril Terrioux <>
Submitted on : Saturday, June 22, 2019 - 11:16:59 PM
Last modification on : Thursday, June 27, 2019 - 1:40:31 AM

File

JFPC_2019_paper_12.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02162856, version 1

Collections

Citation

Djamal Habet, Cyril Terrioux. Une heuristique basée sur l'historique des conflits pour les problèmes de satisfaction de contraintes. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. pp.153-154. ⟨hal-02162856⟩

Share

Metrics

Record views

54

Files downloads

6