IGC : Une nouvelle consistance partielle pour les CSPs continus

Gilles Chabert 1 Gilles Trombettoni 1 Bertrand Neveu 1
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
Résumé : Dans cet article, nous proposons une nouvelle classe de consistances partielles sur les CSPs continus, jusque-là ignorée. Cette approche est motivée par le caractère infructueux des algorithmes de propagation de type AC3 conçus pour des problèmes discrets, et appliqués tels quels en domaine continu, c'est à dire avec la même notion de support (au sens des valeurs réelles). Nous donnons une nouvelle définition, celle de support-intervalle, coïncidant avec une autre abstraction du problème, et déclinons plusieurs propriétés des CSPs liées à cette définition. Nous montrons que seule l'une d'elles (IGC) semble exploitable, et qu'il est possible à partir de l'algorithme de base AC3 de l'obtenir, moyennant le recours à des ROBDD (reduced ordered binary decision diagrams), au lieu de simples intervalles, pour la représentation des domaines.
Type de document :
Communication dans un congrès
Christine Solnon. Premières Journées Francophones de Programmation par Contraintes, Jun 2005, Lens, Université d'Artois, pp.199-210, 2005, Premières Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

https://hal.inria.fr/inria-00000065
Contributeur : Christine Solnon <>
Soumis le : jeudi 26 mai 2005 - 10:01:22
Dernière modification le : mercredi 15 avril 2015 - 16:08:17
Document(s) archivé(s) le : jeudi 1 avril 2010 - 21:32:51

Fichiers

Identifiants

  • HAL Id : inria-00000065, version 1

Collections

Citation

Gilles Chabert, Gilles Trombettoni, Bertrand Neveu. IGC : Une nouvelle consistance partielle pour les CSPs continus. Christine Solnon. Premières Journées Francophones de Programmation par Contraintes, Jun 2005, Lens, Université d'Artois, pp.199-210, 2005, Premières Journées Francophones de Programmation par Contraintes. 〈inria-00000065〉

Partager

Métriques

Consultations de
la notice

170

Téléchargements du document

94