Heuristiques de choix de voisinage pour les recherches à voisinage variable dans les WCSP

Nicolas Levasseur 1 Patrice Boizumault 1 Samir Loudni 1
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Résumé : Le formalisme des Weighted CSP [5, 11] est un cadre général pour modéliser et résoudre des problèmes d'optimisation sous contraintes. VNS/LDS+CP [6] est une méthode hybride basée sur un schéma de recherche locale à voisinages de taille variable (VNS) [7]. Dans ce type de méthodes, le choix des voisinages à explorer joue un rôle primordial. Les très rares heuristiques développées dans le cadre CSP, comme ConflictVar, s'appuient sur les variables en conflit. Dans cet article, nous proposons de nouvelles heuristiques de choix de voisinage pour les WCSPs. Ces heuristiques, outre la notion de conflit, exploitent à la fois la topologie du graphe de contraintes et les poids qui leur sont associés. Les expérimentations réalisées avec VNS/LDS+CP montrent que nos heuristiques guident plus efficacement la recherche que ConflictVar.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.247-256, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00292651
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 11:36:45
Dernière modification le : mardi 5 juin 2018 - 10:14:40
Document(s) archivé(s) le : vendredi 28 mai 2010 - 23:04:17

Fichier

pages-247-256-article14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292651, version 1

Citation

Nicolas Levasseur, Patrice Boizumault, Samir Loudni. Heuristiques de choix de voisinage pour les recherches à voisinage variable dans les WCSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.247-256, 2008. 〈inria-00292651〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

611