Examinando por Autor "Rodriguez-Tello, Eduardo"

Mostrando 1 - 2 de 2

A variable neighborhood search approach for cyclic bandwidth sum problem
(Knowledge-based Systems (Elsevier), 2022-06-21) Cavero, Sergio; G Pardo, Eduardo; Abraham, Duarte; Rodriguez-Tello, Eduardo
In this paper, we tackle the Cyclic Bandwidth Sum Problem, consisting in minimizing the sum of the bandwidth of the edges of an input graph computed in a cycle-structured host graph. This problem has been widely studied in the literature due to its multiple real-world applications, such as circuit design, migration of telecommunication networks, or graph drawing, among others. Particularly, we tackle this problem by proposing a multistart procedure whose main components are a new greedy constructive algorithm and an intensification strategy based on the Variable Neighborhood Search metaheuristic. The constructive procedure introduces two different greedy criteria to determine each step of the construction phase, which can be used for other related problems. Additionally, we illustrate how to perform an efficient exploration of the neighborhood structure by using an alternative neighborhood. Our algorithmic proposal is evaluated over a set of 40 instances previously studied in the literature and over a new proposed set of 66 well-known instances introduced in this paper. The obtained results have been satisfactory compared with the ones obtained by the best previous algorithm in the state of the art. The statistical tests performed indicate that the differences between the methods are significant.
Two-dimensional bandwidth minimization problem: Exact and heuristic approaches
(KNOWLEDGE-BASED SYSTEMS, 2021-02-28) Rodríguez-García, Miguel Ángel; Sánchez-Oro, Jesús; Rodriguez-Tello, Eduardo; Monfroy, Éric; Duarte, Abraham
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. (C) 2020 Elsevier B.V. All rights reserved.