Calcul d'approximations intérieures pour la résolution de Max-NCSP

Marc Christie 1 Jean-Marie Normand 1 Charlotte Truchet 1
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
Résumé : Cet article présente un algorithme de calcul de solutions garanties pour des problèmes numériques MaxCSP. Les auteurs proposent une approche qui offre une exploration complète et garantie de l'espace de recherche et identifie l'ensemble des sous-espaces éventuellement disjoints qui satisfont le plus grand nombre de contraintes numériques du CSP. L'implémentation de cet algorithme fournit une approximation intérieure de ces sous-ensembles pour une taille minimale de pavé donnée. L'approche repose sur des méthodes de propagation classiques sur les intervalles (AC-3) et sur un processus d'extension par l'intérieur en n dimensions. Une hybridation avec des méthodes locales de recherche, étendues aux intervalles, est proposée et testée. Les résultats, portant sur des problèmes jouets montrent l'apport par rapport à un algorithme na¨ıf mais ne mettent pas en lumière l'évidence de la contribution des méthodes de recherche locale.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00085801
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 13:54:39
Dernière modification le : jeudi 5 avril 2018 - 10:36:25
Document(s) archivé(s) le : lundi 5 avril 2010 - 22:03:45

Fichier

33.pdf

Identifiants

  • HAL Id : inria-00085801, version 1

Collections

JFPC06 | UNIV-NANTES | LINA | LINA-TASC

Citation

Marc Christie, Jean-Marie Normand, Charlotte Truchet. Calcul d'approximations intérieures pour la résolution de Max-NCSP. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085801〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

562

Téléchargements de fichiers

486

Contact


archive-ouverte@inria.fr