Particle swarm optimization and hill climbing for the bandwidth minimization problem

摘要

In this paper, the problem of reducing the bandwidth of sparse matrices by permuting rows and columns is addressed and solved with a new hybrid heuristic which combines the Particle Swarm Optimization method with Hill Climbing (PSO-HC). This hybrid approach exploits a compact PSO in order to generate high-quality renumbering which is then refined by means of an efficient implementation of the HC local search heuristic. Computational experiments are carried out to compare the performance of PSO-HC with that of the well-known GPS algorithm, as well as some recently proposed methods, including WBRA, Tabu Search, and GRASP_PR. PSO-HC proves to be extremely stable and reliable in finding good solutions to the bandwidth minimization problem, outperforming the currently known best algorithms in terms of solution quality, in reasonable computational time.