Optimizing the two-dimensional bandwidth problem under the maximum norm using exact and heuristic approaches

Resumen

This paper addresses the Two-dimensional Bandwidth Minimization Problem (2D-BMP) using the L∞-norm distance, focusing on embedding a guest graph into a grid-like host graph to minimize the maximum edge distance. While previous research has emphasized theoretical aspects and regular graphs, practical methods for complex graphs remain underexplored. Solving 2D-BMP is crucial for applications such as VLSI design, network simulation, and scheduling, though its NP-hard nature poses significant challenges. We propose three exact Constraint Satisfaction Problem (CSP) models—arithmetic, finite domain, and dichotomic optimization to efficiently solve the 2D-BMP. Additionally, we introduce the Convergence-Based Multi-start Algorithm (CBMA), a heuristic combining greedy construction and local search for approximate solutions. Our CSP exact methods found optimal solutions for 70 small benchmark instances from diverse standard graph topologies, including 21 previously unknown. On the other hand, the CBMA achieved new upper bounds, requiring moderate computational times, for 113 graphs extracted from the Harwell-Boeing Sparse Matrix Collection which present larger and more complex structures.

Sergio Cavero

Doctor en Inteligencia Artificial

Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.

Eduardo García Pardo

Catedrático de Universidad

Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.