Authors: Mladenović, Nenad 
Urošević, Dragan 
Pérez-Brito, Dionisio
García-González, Carlos
Title: Variable neighbourhood search for bandwidth reduction
Journal: European Journal of Operational Research
Volume: 200
Issue: 1
First page: 14
Last page: 27
Issue Date: 1-Jan-2010
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2008.12.015
The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.
Keywords: Combinatorial optimization | Matrix bandwidth minimization | Metaheuristics | Variable neighbourhood search
Publisher: Elsevier
Project: Serbian Academy of Sciences, Project number 144007
Spanish grant MTM2007-67433-CO2-01

Show full item record


checked on Dec 6, 2023

Page view(s)

checked on Dec 7, 2023

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.