A greedy randomized adaptive search procedure and path relinking for the matrix bandwidth minimization

In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the non-zero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a path relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with path relinking is also found to be competitive with a recently published Tabu search algorithm that is considered one of the best currently available for bandwidth minimization.