Variable neighbourhood search for bandwidth reduction

Nenad Mladenovic, Dragan Urosevic, Pérez-Brito, Dionisio and García-González, Carlos G.

European Journal of Operational Research, 2010, vol. 200, issue 1, pages 14-27

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 (search for similar items in EconPapers)
Date: 2010

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... a81d58454542417b51cc
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:1:p:14-27

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().