A Dual Representation Simulated Annealing Algorithm for the Bandwidth Minimization Problem on Graphs

Published

January 16, 2015

Author(s)

Jose Torres Jimenez, Javier Bernal, Raghu N. Kacker

Abstract

The bandwidth minimization problem on graphs (BMPG) consists of labeling the vertices of a graph with the integers from 1 to $n$ ($n$ is the number of vertices) such that the maximum absolute difference between labels of adjacent vertices is as small as possible. In this work we develop a DRSA (dual representation simulated annealing) algorithm to solve BMPG. The main novelty of DRSA is an internal dual representation of the problem used in conjunction with a neighborhood function composed of three perturbation operators. The evaluation function of DRSA is able to discriminate among solutions of equal bandwidth by taking into account all absolute differences between labels of adjacent vertices. For better performance, the parameters of DRSA and the probabilities for selecting the perturbation operators were tuned by extensive experimentation carried out using a full factorial design. The benchmark for the proposed algorithm consists of 113 instances of the Harwell-Boeing sparse matrix collection; the results of DRSA included 31 new upper bounds and the matching of 82 best-known solutions (22 solutions are optimal). We used Wilcoxon signed-rank test to compare best solutions produced by DRSA against best solutions produced by three state of the art methods: greedy randomized adaptive search procedure with path relinking, simulated annealing, and variable neighborhood search; according to the comparisons done, the quality of the solutions with DRSA is significantly better than that obtained with the other three algorithms.

Citation

Information Sciences

Volume

303

Pub Type

Journals

Download Paper

DOI Link

Keywords

Bandwidth minimization, Simulated annealing, Combinatorial optimization, Meta-Heuristics

Citation

Torres, J. , Bernal, J. and Kacker, R. (2015), A Dual Representation Simulated Annealing Algorithm for the Bandwidth Minimization Problem on Graphs, Information Sciences, [online], https://doi.org/10.1016/j.ins.2014.12.041 (Accessed April 25, 2024)