Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/inria-00292651
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, July 2, 2008 - 11:36:45 AM
Last modification on : Thursday, February 7, 2019 - 5:47:38 PM
Long-term archiving on: : Friday, May 28, 2010 - 11:04:17 PM

File

pages-247-256-article14.pdf
Files produced by the author(s)

Identifiers

  • 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. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.247-256. ⟨inria-00292651⟩

Share

Metrics

Record views

235

Files downloads

767