Exploitation de la décomposition arborescente pour guider la recherche VNS

Mathieu Fontaine 1 Samir Loudni 1 Patrice Boizumault 1
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide the exploration of local search methods that use large neighborhoods like VNS. We introduce tightness dependant tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Experiments performed on random instances (GRAPH) and real life instances (CELAR and SPOT5) show the appropriateness and the efficiency of our approach.
Type de document :
Communication dans un congrès
JFPC 2012, May 2012, toulouse, France. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00810146
Contributeur : Mathieu Fontaine <>
Soumis le : vendredi 26 avril 2013 - 11:11:18
Dernière modification le : mardi 5 juin 2018 - 10:14:40
Document(s) archivé(s) le : samedi 27 juillet 2013 - 02:30:10

Fichier

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

Identifiants

  • HAL Id : hal-00810146, version 1

Citation

Mathieu Fontaine, Samir Loudni, Patrice Boizumault. Exploitation de la décomposition arborescente pour guider la recherche VNS. JFPC 2012, May 2012, toulouse, France. 2012. 〈hal-00810146〉

Partager

Métriques

Consultations de la notice

197

Téléchargements de fichiers

75