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 | Abstract: | 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
SCOPUSTM
Citations
50
checked on Nov 11, 2024
Page view(s)
16
checked on Nov 11, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.