Abstract
Reducing the bandwidth in a graph is an optimization problem which has generated significant attention over time due to its practical application in Very Large Scale Integration (VLSI) layout designs, solving system of equations, or matrix decomposition, among others. The bandwidth problem is considered as a graph labeling problem where each vertex of the graph receives a unique label. The target consists in finding an embedding of the graph in a line, according to the labels assigned to each vertex, that minimizes the maximum distance between the labels of adjacent vertices. In this work, we are focused on a 2D variant where the graph has to be embedded in a two-dimensional grid instead. To solve it, we have designed two constructive and three local search methods which are integrated in a Basic Variable Neighborhood Search (BVNS) scheme. To assess their performance, we have designed three Constraint Satisfaction Problem (CSP) models. The experimental results show that our CSP models obtain remarkable results in small or medium size instances. On the other hand, BVNS is capable of reaching equal or similar results than the CSP models in a reduced run-time for small instances, and it can provide high quality solutions in those instances which are not optimally solvable with our CSP models.
Miguel Ángel Rodriguez García
Phd in Artificial Intelligence
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.