Bringing order into the neighborhoods: relaxation guided variable neighborhood search - Archive ouverte HAL Access content directly
Journal Articles Journal of Heuristics Year : 2008

Bringing order into the neighborhoods: relaxation guided variable neighborhood search

(1) , (2)
1
2

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.
Fichier principal
Vignette du fichier
puchinger-06a.pdf (200.71 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01224918 , version 1 (09-11-2015)

Identifiers

Cite

Jakob Puchinger, Günther R. Raidl. Bringing order into the neighborhoods: relaxation guided variable neighborhood search. Journal of Heuristics, 2008, 14 (5), pp.457-472. ⟨10.1007/s10732-007-9048-9⟩. ⟨hal-01224918⟩
80 View
233 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More