Grid Bandwidth Minimization Problem: Simulated Annealing Approach
Aditi Khandelwal, Kamal Kumar Srivastava, Gur Saran · Mapana Journal of Sciences · 2023
The Grid Bandwidth Minimization Problem (GBMP) is to find an embedding of a given graph into a host graph such that the bandwidth over all edges is minimised. It is an NP-complete problem with applications in VLSI circuit design, numerical analysis, computational biology, graph theory and scheduling. In this paper, a Simulated Annealing (SA) algorithm is developed for GBMP in which initial solution is generated using two problem-specific construction heuristics. Four neighborhood strategies are designed to explore the search space. Experiments conducted on benchmark instances achieve results which fall within the bounds whereas for grid graphs it attains optimal values.