Efficient Iterated Greedy for the Two-Dimensional Bandwidth Minimization Problem
Graph layout problems are a family of combinatorial optimization problems that consist of finding an embedding of the vertices of an input graph into a host graph such that an objective function is optimized. Within this family of problems falls the so-called Two-Dimensional Bandwidth Minimization Problem (2DBMP). The 2DBMP aims to minimize the maximum distance between each pair of adjacent vertices of the input graph when it is embedded into a grid host graph. In this paper, we present an efficient heuristic algorithm based on the Iterated Greedy (IG) framework hybridized with a new local search strategy to tackle the 2DBMP. Particularly, we propose different designs for the main IG procedures (i.e., construction, destruction, and reconstruction) based on the trade-off between intensification and diversification. Additionally, the improvement method incorporates three advanced strategies: an efficient way to evaluate the objective function of neighbor solutions, a tiebreak criterion to deal with “flat landscapes”, and a neighborhood reduction technique. Extensive experimentation was carried out to assess the IG performance over state-of-the-art methods, emerging our approach as the most competitive algorithm. Specifically, IG finds the best solutions for all instances considered in considerably less execution time. Statistical tests corroborate the merit of our proposal.
This research has been partially supported by the Ministerio de Ciencia, Innovación y Universidades (Grant Ref. PGC2018-095322-B-C22, PID2021-125709OA-C22 and FPU19/04098) and by the Comunidad de Madrid and the European Regional Development Fund (Grant Ref. P2018/TCS-4566). We also thank M.A. Rodrguez et al., authors of the previous most competitive method in the state of the art Rodríguez-García et al. (2021) for sharing their code with us.
- Artículos de Revista