6533b82bfe1ef96bd128df10

RESEARCH PRODUCT

GRASP and path relinking for the matrix bandwidth minimization

Vicente CamposEstefanía PiñanaIsaac PlanaRafael Martí

subject

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceGRASPManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringTabu searchMatrix (mathematics)Modeling and SimulationPath (graph theory)Bandwidth (computing)HeuristicsMetaheuristicGreedy randomized adaptive search procedureMathematics

description

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 nonzero 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.

yearjournalcountryeditionlanguage
2004-02-01European Journal of Operational Research
https://doi.org/10.1016/s0377-2217(02)00715-4