Examinando por Autor "Pardo, Eduardo G."

Mostrando 1 - 8 de 8

A general variable neighborhood search for the cyclic antibandwidth problem
(Computational Optimization and Applications (Springer), 2022-01-17) Cavero, Sergio; Pardo, Eduardo G.; Duarte, Abraham
Graph Layout Problems refer to a family of optimization problems where the aim is to assign the vertices of an input graph to the vertices of a structured host graph, optimizing a certain objective function. In this paper, we tackle one of these problems, named Cyclic Antibandwidth Problem, where the objective is to maximize the minimum distance of all adjacent vertices, computed in a cycle host graph. Specifically, we propose a General Variable Neighborhood Search which combines an efficient Variable Neighborhood Descent with a novel destruction–reconstruction shaking procedure. Additionally, our proposal takes advantage of two new exploration strategies for this problem: a criterion for breaking the tie of solutions with the same objective function and an efficient evaluation of neighboring solutions. Furthermore, two new neighborhood reduction strategies are proposed. We conduct a thorough computational experience by comparing the algorithm proposed with the current state-of-the-art methods over a set of previously reported instances. The associated results show the merit of the introduced algorithm, emerging as the best performance method in those instances where the optima are unknown. These results are further confirmed with nonparametric statistical tests.
An efficient heuristic algorithm for software module clustering optimization
(Elsevier, 2022-08) Yuste, Javier; Duarte, Abraham; Pardo, Eduardo G.
In the lifecycle of software projects, maintenance tasks usually entail 75% of the total costs, where most efforts are spent in understanding the program. To improve the maintainability of software projects, the code is often divided into components, which are then grouped in different modules following good design principles, lowering coupling and increasing cohesion. The Software Module Clustering Problem (SMCP) is an optimization problem that looks for maximizing the modularity of software projects in the context of Search-Based Software Engineering. In the SMCP, projects are often modeled as graphs. Therefore, the SMCP can be interpreted as a graph partitioning problem, which is proved to be NP-hard. In this work, we propose a new heuristic algorithm for software modularization, based on a Greedy Randomized Adaptive Search Procedure with Variable Neighborhood Descent. We present a three-fold categorization of neighborhoods for the SMCP and leverage domain-specific information to filter unpromising solutions. Our proposal has been successfully tested over a dataset of real software projects, outperforming the previous state-of-the-art approach in terms of Modularization Quality in very short computing times. Therefore, it could be integrated in software development tools to improve the quality of software projects in real time.
General Variable Neighborhood Search for the optimization of software quality
(Elsevier, 2024-05) Yuste, Javier; Pardo, Eduardo G.; Duarte, Abraham
In the area of Search-Based Software Engineering, software engineering issues are formulated and tackled as optimization problems. Among the problems within this area, the Software Module Clustering Problem (SMCP) consists of finding an organization of a software project that minimizes coupling and maximizes cohesion. Since modular code is easier to understand, the objective of this problem is to increase the quality of software projects, thus increasing their maintainability and reducing the associated costs. In this work we study a recently proposed objective function named Function of Complexity Balance (FCB). Since this problem has been demonstrated to be -hard, we propose a new heuristic algorithm based on the General Variable Neighborhood Search (GVNS) schema to tackle the problem. For the GVNS, we propose six different neighborhood structures and categorize them into three different groups. Then, we analyze their contribution to the results obtained by the algorithm. In order to improve the efficiency of the proposed approach, we leverage domain-specific information to perform incremental evaluations of the objective function and to explore only areas of interest in the search space. The proposed algorithm has been tested over a set of real world software repositories, achieving better results than the previous state-of-the-art method, a Hybrid Genetic Algorithm, in terms of both quality and computing times. Furthermore, the relevance of the improvement produced by our proposal has been corroborated by non-parametric statistical tests
Multi-armed bandit for the cyclic minimum sitting arrangement problem
(Elsevier, 2025-07) Robles, Marcos; Cavero, Sergio; Pardo, Eduardo G.; Cordón, Oscar
Graphs are commonly used to represent related elements and relationships among them. Signed graphs are a special type of graphs that can represent more complex structures, such as positive or negative connections in a social network. In this work, we address a combinatorial optimization problem, known as the Cyclic Minimum Sitting Arrangement, that consists of embedding a signed input graph into a cycle host graph, trying to locate in the embedding positive connected vertices closer than negative ones. This problem is a variant of the well-known Minimum Sitting Arrangement where the host graph has the structure of a path graph. To tackle the problem, we propose an algorithm based on the Multi-Armed Bandit method that combines three greedy-randomized constructive procedures with a Variable Neighborhood Descent local search algorithm. To assess the merit of our proposal, we compare it with the state-of-the-art method. Our experiments show that our algorithm outperforms the best-known method in the literature to date, and the results are statistically significant, establishing itself as the new state of the art for the problem.
Multi-objective general variable neighborhood search for software maintainability optimization
(Elsevier, 2024-07) Yuste, Javier; Pardo, Eduardo G.; Duarte, Abraham; Hao, Jin-Kao
The quality of software projects is measured by different attributes such as efficiency, security, robustness, or understandability, among others. In this paper, we focus on maintainability by studying the optimization of software modularity, which is one of the most important aspects in this regard. Specifically, we study two well-known and closely related multi-objective optimization problems: the Equal-size Cluster Approach Problem (ECA) and the Maximizing Cluster Approach Problem (MCA). Each of these two problems looks for the optimization of several conflicting and desirable objectives in terms of modularity. To this end, we propose a method based on the Multi-Objective Variable Neighborhood Search (MO-VNS) methodology in combination with a constructive procedure based on Path-Relinking. As far as we know, this is the first time that a method based on MO-VNS is proposed for the MCA and ECA problems. To enhance the performance of the proposed algorithm, we present three advanced strategies: an incremental evaluation of the objective functions, an efficient exploration of promising areas in the search space, and an analysis of the objectives that better serve as guiding functions during the search phase. Our proposal has been validated by experimentally comparing the performance of our algorithm with the best previous state-of-the-art method for the problem and three reference methods for multi-objective optimization. The experiments have been performed on a set of 124 real software instances previously reported in the literature
Multistart Search for the Cyclic Cutwidth Minimization Problem
(Computers & Operations Research (Elsevier), 2021) Cavero, Sergio; Pardo, Eduardo G.; Laguna, Manuel; Duarte, Abraham
English: The Cyclic Cutwidth Minimization Problem (CCMP) is a Graph Layout Problem that consists of finding an embedding of the vertices of a candidate graph in a host graph, in order to minimize the maximum cut of a host edge. In this case, the host graph is restricted to be a cycle. In this paper, we identify a new lower bound for the problem, and also a property which allows search procedures to drastically reduce the neighborhood size during the search. Additionally, we propose the use of an alternative objective function for min–max optimization problems, never used before in the context of the CCMP. These strategies have been combined within a multistart search procedure for this problem. The obtained method is compared with the state of the art for the CCMP using sets of problem instances previously published. Statistical tests indicate the merit of our proposal. Español: El problema de minimización del ancho de corte cíclico (CCMP) es un problema de grados que consiste en encontrar un embebido de los vértices de un grafo candidato en un grafo huésped, con el fin de minimizar el máximo corte de una arista del grafo huésped. En este caso, el grafo huésped se restringe a ser un ciclo. En este artículo, identificamos una nueva cota inferior para el problema, y también una propiedad que permite a los procedimientos de búsqueda reducir drásticamente el tamaño del vecindario durante la búsqueda. Además, proponemos el uso de una función objetivo alternativa para los problemas de optimización min-max, nunca utilizada antes en el contexto del CCMP. Estas estrategias se han combinado dentro de un procedimiento de búsqueda multistart para este problema. El método obtenido se compara con el estado del arte para el CCMP utilizando conjuntos de instancias de problemas publicados anteriormente. Las pruebas estadísticas indican el mérito de nuestra propuesta.
Solving a short sea inventory routing problem in the oil industry
(Elsevier, 2024-03) Cavero, Sergio; Laguna, Manuel; Pardo, Eduardo G.
We address an optimization problem related to the minimization of the distribution costs associated with product delivery in the oil industry. Particularly, the problem consists of determining a schedule of shipments from production ports to satisfy demand and desired inventory limits at consumptions ports. Products are transported in vessels, which can be viewed as a set of shared resources. The complexity of the problem derives from the problem structure and the number of decisions that need to be made throughout a planning horizon. The context that we studied belongs to the family of short sea inventory routing problems for which the ports are in the same geographical area. We formulate a mixed-integer programming model that captures the most relevant features of the real system. The main decisions include the selection of the vessels that will be used, the paths that each vessel will follow, and the quantities of each product loaded and unloaded at each port visited during the planning horizon. We test the limits of our mathematical programming formulation and develop a heuristic approach for tackling problem sizes that exceed the capabilities of a commercial solver
Strategic oscillation tabu search for improved hierarchical graph drawing
(Expert Systems with Applications (Elsevier), 2024-01-01) Cavero, Sergio; Pardo, Eduardo G.; Glover, Fred; Martí, Rafael
In the last years, many areas in science, business, and engineering have experienced an enormous growth in the amount of data that they are required to analyze. In many cases, this analysis relies intimately on data visualization and, as a result, graph drawing has emerged as a new field of research. This paper addresses the challenge of drawing hierarchical graphs, which is one of the most widely used drawing standards. We introduce a new mathematical model to automatically represent a graph based on the alignment of long arcs, which we combine with the classic arc crossing minimization objective in hierarchical drawings. We complement our proposal with a heuristic algorithm that can obtain high-quality results in the short computational time required by graph drawing systems. Our algorithm joins two methodologies, tabu search and strategic oscillation (SOS), to perform a fast and effective exploration of the search space. We conduct extensive experimentation that integrates our new mathematical programming formulation and the SOS tabu search that targets large instances. Our statistical analysis confirms the effectiveness of this proposal.