Estimer le nombre de solutions des contraintes de cardinalité grâce à leur décomposition range et roots - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

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

(1) , (2) , (3)
1
2
3
Xavier Lorca

Abstract

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.
Fichier principal
Vignette du fichier
estimer-le-nombre-de-solutions.pdf (2.39 Mo) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-02160312 , version 1 (20-06-2019)

Identifiers

  • HAL Id : hal-02160312 , version 1

Cite

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⟩
93 View
38 Download

Share

Gmail Facebook Twitter LinkedIn More