Un nouvel algorithme de consistance locale sur les nombres flottants

Résumé : La résolution de contraintes sur les nombres a virgule flottante soulève des problèmes critiques dans de nombreuses applications, notamment en vérification de programmes. Jusqu'à maintenant, les algorithmes de filtrage sur les nombres à virgule flottante ont été limités a la 2B{consistance et ses dérivées. Bien que ces filtrages soient conservatifs des solutions, ils souffrent des problèmes bien connus des consistances locales, e.g., leur incapacité à traiter efficacement les occurrences multiples de variables. Leurs limitations proviennent aussi de la pauvret e des propriétés de l'arithmétique des nombres à virgule flottante. Afin de pallier à ces limitations, nous proposons dans cet article un nouvel algorithme de filtrage de contraintes sur les flottants qui repose sur des relaxations successives sur les réels du problème initial sur les flottants. Des bornes conservatives des domaines sont obtenues à l'aide d'un solveur de programme linéaire mixte (MILP) appliquées à des linéarisations conservatives de ces relaxations. Les résultats préliminaires sont prometteurs et montrent que cette approche peut effectivement accélérer les filtrages par consistances locales.
Type de document :
Communication dans un congrès
Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

https://hal.inria.fr/hal-00829579
Contributeur : Ist Inria Saclay <>
Soumis le : lundi 3 juin 2013 - 15:03:13
Dernière modification le : mardi 4 juin 2013 - 15:37:03
Document(s) archivé(s) le : mercredi 4 septembre 2013 - 04:13:48

Fichier

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

Identifiants

  • HAL Id : hal-00829579, version 1

Collections

Citation

Mohammed Said Belaid, Claude Michel, Michel Rueher. Un nouvel algorithme de consistance locale sur les nombres flottants. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. <hal-00829579>

Partager

Métriques

Consultations de
la notice

106

Téléchargements du document

197