ACID : Disjonction constructive adaptative sur intervalles

Bertrand Neveu 1, 2 Gilles Trombettoni 3
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Un opérateur de filtrage nommé CID et une variante efficace 3BCID ont eté proposés en 2007. Ces opérateurs calculent pour des CSP numériques traités avec des méthodes à intervalles une consistance partielle équivalente à Partition-1-AC pour les CSP à domaines finis. Les deux paramètres principaux de CID sont le nombre d'appels à la procédure principale et le nombre maximum de sous-intervalles traités par cette procédure. Cet opérateur 3BCID est efficace pour la résolution de CSP numériques, mais l'est moins en optimisation globale sous contraintes. Cet article propose une variante adaptative de 3BCID. Le nombre de variables traitées est calculé automatiquement durant la recherche, les autres paramètres étant fixés de manìère robuste. Sur un échantillon représentatif d'instances, ACID apparaît comme la meilleure approche en résolution et en optimisation. Elle a été choisie comme méthode de contraction par défaut du résolveur par intervalles Ibex.
Type de document :
Communication dans un congrès
JFPC: Journées Francophones de Programmation par Contraintes, Jun 2014, Angers, France. 11iemes Journées Francophones de Programmation par Contraintes, 2014, 〈http://jfpc-jiaf2014.univ-angers.fr/jfpc/index.php〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal-enpc.archives-ouvertes.fr/hal-01077462
Contributeur : Bertrand Neveu <>
Soumis le : vendredi 24 octobre 2014 - 17:15:04
Dernière modification le : mardi 16 octobre 2018 - 01:02:08
Document(s) archivé(s) le : dimanche 25 janvier 2015 - 10:50:51

Fichier

acidjfpc1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01077462, version 1

Citation

Bertrand Neveu, Gilles Trombettoni. ACID : Disjonction constructive adaptative sur intervalles. JFPC: Journées Francophones de Programmation par Contraintes, Jun 2014, Angers, France. 11iemes Journées Francophones de Programmation par Contraintes, 2014, 〈http://jfpc-jiaf2014.univ-angers.fr/jfpc/index.php〉. 〈hal-01077462〉

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

225