A Reduced Variable Neighbourhood Search Algorithm for Grid Bandwidth Minimization Problem
Aditi Khandelwal, Kamal Kumar Srivastava, Gur Saran · 2023
For a given graph G, the dilation problem or the grid bandwidth minimization problem (GBMP) seeks to find an embedding of the host graph G onto a guest grid graph H such that the bandwidth of the embedding over all edges is minimized. The Dilation Problem is NP-hard in general. In this paper, a reduced variable neighbourhood search (RVNS) algorithm is developed for GBMP of an l×m grid embedding. This research study has designed four construction heuristics and the best quality solution among them is used as an initial solution for the RVNS procedure. Two new neighbourhood search operators and a shaking procedure are designed to explore the search space. The test suite used for experiments consists of a subset of Harwell-Boeing graphs, grid graphs and cycles. The computational results show that the algorithm is able to achieve optimal results for grid graphs and cycles. Comparison of RVNS with existing approaches shows improvement in results for most Harwell-Boeing instances.