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

Abstract

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

Phd in Artificial Intelligence

Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.

Eduardo García Pardo

Full Professor

One of the founders of the investigation group GRAFO, whose main line of research is the development of algorithms to tackle optimization problems, the topic of the researcher’s Doctoral Thesis and which their most notable publications are framed.