Vol. 22 No. Special Issue (2023): Mapana Journal of Sciences- RECENT DEVELOPMENTS IN PURE AND APPLIED MATHEMATICS
Research Articles

Grid Bandwidth Minimization Problem: Simulated Annealing Approach

PDF
  • Aditi Khandelwal,
  • Kamal Srivastava,
  • Gur Saran
Aditi Khandelwal
DAYALBAGH EDUCATIONAL INSTITUTE
DOI: https://doi.org/10.12723/mjs.sp1.9

Published 2023-07-19

Keywords

  • Grid embedding,
  • Bandwidth,
  • Simulated Annealing

Copyright (c) 2023

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Abstract

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.

PDF

References

  1. Chung, Fan RK. "Labelings of graphs." Selected topics in graph theory 3, no. 25 (1988): 151-168.
  2. Dıaz, Josep, Jordi Petit, and Marıa Serna. "A Survey on Graph Layout Problems." (2000).
  3. Caprara, A., & Salazar-González, J. J. (2005). Laying out sparse graphs with provably minimum bandwidth. INFORMS Journal on Computing, 17(3), 356-373.
  4. Raspaud, A., Sýkora, O., & Vrto, I. (2000, June). Congestion and dilation, similarities and differences: A survey. In SIROCCO (pp. 269-280).
  5. Blum, A., Konjevod, G., Ravi, R., & Vempala, S. (2000). Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoretical Computer Science, 235(1), 25-42.
  6. Gupta, A. (2001). Improved bandwidth approximation for trees and chordal graphs. Journal of Algorithms, 40(1), 24-36.
  7. Torres-Jimenez, J., Izquierdo-Marquez, I., Garcia-Robledo, A., Gonzalez-Gomez, A., Bernal, J., & Kacker, R. N. (2015). A dual representation simulated annealing algorithm
  8. for the bandwidth minimization problem on graphs. Information Sciences, 303, 33-49.
  9. Mladenovic, N., Urosevic, D., Pérez-Brito, D., & García-González, C. G. (2010). Variable neighbourhood search for bandwidth reduction. European Journal of Operational Research, 200(1), 14-27.
  10. Rodríguez-García, Miguel Ángel, Jesus Sanchez-Oro, Eduardo Rodriguez-Tello, Eric Monfroy, and Abraham Duarte. "Two-dimensional bandwidth minimization problem:Exact and heuristic approaches." Knowledge-Based Systems 214 (2021): 106651.
  11. Miller, Zevi, and James B. Orlin. "NP-completeness for minimizing maximum
  12. edge length in grid embeddings." Journal of algorithms 6, no. 1 (1985): 10-16.
  13. Hong, Jia-Wei, Kurt Mehlhorn, and Arnold L. Rosenberg. "Cost trade-offs in graph embeddings, with applications." Journal of the ACM (JACM) 30, no. 4 (1983):709-728.
  14. Bezrukov, Sergei L., Joe D. Chavez, Larry H. Harper, Markus Röttger, and U-P. Schroeder. "Embedding of hypercubes into grids." In International Symposium on Mathematical Foundations of Computer Science, pp. 693-701. Springer, Berlin,
  15. Heidelberg, 1998.
  16. Bhatt, S. N., & Leighton, F. T. (1984). A framework for solving VLSI graph
  17. layout problems. Journal of Computer and System Sciences, 28(2), 300-343.
  18. Lin, Y. "On density lower bounds of two-dimensional bandwidth." In Journal Of Mathematical Research And Exposition-Chinese Edition-, vol. 16, pp. 343-349. Mathematical Research and Exposition, 1996.
  19. Lin, Lan, and Yixun Lin. "Square-root rule of two-dimensional bandwidth problem∗." RAIRO-Theoretical Informatics and Applications 45, no. 4 (2011): 399- 411. https://doi.org/10.1051/ita/2011120
  20. J.-X. Hao, Two-dimensional Bandwidth of Mobius Ladders and Other Graphs, Henan Sci. 18 (1) (2000) 15–20.
  21. Rodríguez-García, M. A., Duarte, A., & Sánchez-Oro, J. (2018, May). GRASP with Path Relinking for 2D-Bandwidth Minimization Problem. In Proceedings of the International Conference on Learning and Optimization Algorithms: Theory and
  22. Applications (pp. 1-5).
  23. Aroca, J. A., & Anta, A. F. (2014, June). JAM: A Tabu-Based Two-Stage Simulated Annealing Algorithm for the Multidimensional Arrangement Problem. In International Workshop on Hybrid Metaheuristics (pp. 155-168). Springer, Cham.
  24. Kirkpatrick, Scott. "Optimization by simulated annealing: Quantitative studies." Journal of statistical physics 34, no. 5 (1984): 975-986.