Bringing order into the neighborhoods: relaxation guided variable neighborhood search

Abstract : In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising for many other combinatorial optimization problems approached by VNS.
Type de document :
Article dans une revue
Journal of Heuristics, Springer Verlag, 2008, 14 (5), pp.457-472. 〈10.1007/s10732-007-9048-9〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01224918
Contributeur : Jakob Puchinger <>
Soumis le : lundi 9 novembre 2015 - 13:17:54
Dernière modification le : dimanche 22 janvier 2017 - 12:13:48
Document(s) archivé(s) le : mercredi 10 février 2016 - 10:10:19

Fichier

puchinger-06a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jakob Puchinger, Günther Raidl. Bringing order into the neighborhoods: relaxation guided variable neighborhood search. Journal of Heuristics, Springer Verlag, 2008, 14 (5), pp.457-472. 〈10.1007/s10732-007-9048-9〉. 〈hal-01224918〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

71