Estimer le nombre de solutions des contraintes de cardinalité grâce à leur décomposition range et roots

Résumé : En programmation par contraintes, le choix d’une heuristique de recherche plutôt qu’une autre dépend souvent du problème. Cependant il existe des heuristiques génériques utilisant plutôt des indicateurs sur la structure combinatoire du problème. Les heuristiques "Counting- Based", introduites par Pesant et al., font des choix basés sur une estimation du nombre de solutions restantes dans tel ou tel sous-arbre de l’arbre de recherche. Un inconvénient de ces heuristiques est qu’elles nécessitent des algorithmes de dénombrement spécifiques à chaque contrainte. Cette étude s’intéresse aux contraintes de cardinalité, dont alldifferent, atmost, nvalue, etc... Nous proposons une méthode de comptage de solutions pour les contraintes range et roots, introduites par Bessiere et al. Grâce à la décomposition des contraintes de cardinalité en contraintes range et roots, nous dérivons une méthode systématique de dénombrement de solutions pour la plupart de ces contraintes.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-mines-albi.archives-ouvertes.fr/hal-02160312
Contributor : Imt Mines Albi Ecole Nationale Supérieure Des Mines d'Albi-Carmaux <>
Submitted on : Thursday, June 20, 2019 - 1:21:12 PM
Last modification on : Monday, July 8, 2019 - 3:56:15 PM

File

estimer-le-nombre-de-solutions...
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-02160312, version 1

Citation

Giovanni Lo Bianco, Xavier Lorca, Charlotte Truchet. Estimer le nombre de solutions des contraintes de cardinalité grâce à leur décomposition range et roots. JFPC 2019 - Actes des 15es Journées Francophones de Programmation par Contraintes, Jun 2019, Albi, France. p. 133-141. ⟨hal-02160312⟩

Share

Metrics

Record views

37

Files downloads

23