R. Martí, M. Laguna, F. Glover and V. Campos
European Journal of Operational Research, vol. 135, no. 2, pp. 211-220 (2001)
The bandwidth of a matrix A={a(i,j)} is defined as the maximum absolute difference between i and j for which a(i,j) is different than zero . The problem of reducing the bandwidth of a matrix consists of finding a permutation of the rows and columns that keeps the nonzero elements in a band that is as close as possible to the main diagonal of the matrix. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the nonzero elements of the corresponding symmetrical matrix. Many bandwidth reduction algorithms have been developed since the 1960s and applied to structural engineering, fluid dynamics and network analysis. For the most part, these procedures do not incorporate metaheuristic elements, which is one of the main goals of our current development. Another equally important goal is to design and test a special type of candidate list strategy to be embedded in a tabu search procedure for the bandwidth reduction problem. This candidate list strategy accelerates the selection of a move in the neighborhood of the current solution in any given iteration. Our extensive experimentation shows that the proposed procedure outperforms the best-known algorithms in terms of solution quality consuming a reasonable computational effort.
Full text
