Examinando por Autor "Sánchez-Oro, Jesús"

Mostrando 1 - 15 de 15

A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem
(Springer, 2022) Casado, Alejandra; Pérez-Peló, Sergio; Sánchez-Oro, Jesús; Duarte, Abraham
The selection of individuals with similar characteristics from a given population have always been a matter of interest in several scientific areas: data privacy, genetics, art, among others. This work is focused on the maximum intersection of k-subsets problem (kMIS). This problem tries to find a subset of k individuals with the maximum number of features in common from a given population and a set of relevant features. The research presents a Greedy Randomized Adaptive Search Procedure (GRASP) where the local improvement is replaced by a complete Tabu Search metaheuristic with the aim of further improving the quality of the obtained solutions. Additionally, a novel representation of the solution is considered to reduce the computational effort. The experimental comparison carefully analyzes the contribution of each part of the algorithm to the final results as well as performs a thorough comparison with the state-of-the-art method. Results, supported by non-parametric statistical tests, confirms the superiority of the proposal.
A reactive path relinking algorithm for solving the bi-objective p-Median and p-Dispersion problem
(Springer, 2023) Lozano Osorio, Isaac; Sánchez-Oro, Jesús; López Sánchez, Ana Dolores; Duarte, Abraham
This paper deals with an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities. The problem is addressed with a novel path relinking approach, called reactive path relinking, which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. Additionally, the proposal is adapted to a multi-objective perspective for finding a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature.
A review on discrete diversity and dispersion maximization from an OR perspective
(Elsevier, 2022-06-16) Pérez-Peló, Sergio; Martí, Rafael; Martínez-Gavara, Anna; Sánchez-Oro, Jesús
El problema de la maximización de la diversidad o la dispersión consiste en seleccionar un subconjunto de elementos de un conjunto dado de tal forma que se maximice la distancia entre los elementos seleccionados. La definición de distancia entre elementos se adapta a aplicaciones específicas, y la forma de calcular la diversidad global de los elementos seleccionados da lugar a distintos modelos matemáticos. La maximización de la diversidad mediante modelos de optimización combinatoria ha ganado importancia en la Investigación Operativa (IO) durante las dos últimas décadas, y constituye hoy en día un área importante. En este trabajo se revisan los hitos en el desarrollo de esta área, comenzando a finales de los ochenta cuando se propusieron los primeros modelos, y se identifican tres periodos de tiempo. El análisis crítico desde una perspectiva OR de los desarrollos anteriores, nos permite establecer los modelos más apropiados, su conexión con los problemas prácticos en términos de dispersión y representatividad, y los problemas abiertos que todavía suponen un reto. También revisamos y ampliamos la biblioteca de instancias de referencia que se ha utilizado ampliamente en las comparaciones heurísticas. Por último, realizamos una revisión empírica y una comparación de los mejores procedimientos y de los propuestos más recientemente, para identificar claramente los métodos más avanzados para los principales modelos de diversidad.
An experimental comparison of Variable Neighborhood Search variants for the minimization of the vertex-cut in layout problems
(Elsevier, 2012) Sánchez-Oro, Jesús; Duarte, Abraham
Variable Neighborhood Search (VNS) is a metaheuristic for solving optimization problems based on a systematic change of neighborhoods. In recent years, a large variety of VNS strategies have been proposed. However, we have only found limited experimental comparisons among different VNS variants. This paper reviews three VNS strategies for finding near-optimal solutions for vertex-cut minimization problems. Specifically, we consider the min-max variant (Vertex Separation Problem) and the min-sum variant (SumCut Minimization Problem). We also present an preliminary computational comparison of the methods on previously reported instances.
Apuntes de la asignatura Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pérez, Sergio; Pantrigo, Juan José; Duarte, Abraham
Diapositivas de Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio
Dynamic Path Relinking for the Target Set Selection problem
(Elsevier, 2023) Lozano-Osorio, Isaac; Oliva-García, Andrea; Sánchez-Oro, Jesús
This research proposes the use of metaheuristics for solving the Target Set Selection (TSS) problem. This problem emerges in the context of influence maximization problems, in which the objective is to maximize the number of active users when spreading information throughout a social network. Among all the influence maximization variants, TSS introduces the concept of reward of each user, which is the benefit associated to its activation. Therefore, the problem tries to maximize the reward obtained among all active users by selecting an initial set of users. Each user has also associated an activation cost, and the total sum of activation costs of the initial set of selected users cannot exceed a certain budget. In particular, two Path Relinking approaches are proposed, comparing them with the best method found in the state of the art. Additionally, a more challenging set of instances are derived from real-life social networks, where the best previous method is not able to find a feasible solution. The experimental results show the efficiency and efficacy of the proposal, supported by non-parametric statistical tests.
Ejercicios de la asignatura Algortimos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio
Finding weaknesses in networks using Greedy Randomized Adaptive Search Procedure
(Wiley, 2020-02-17) Pérez-Peló, Sergio; Sánchez-Oro, Jesús; Duarte, Abraham
En los últimos años, la relevancia de la ciberseguridad ha sido cada vez más evidente para las empresas e instituciones, así como para los usuarios finales. Por ello, es importante garantizar la robustez de una red. Con el objetivo de mejorar la seguridad de la red, es conveniente averiguar cuáles son los nodos críticos de la infraestructura, para protegerlos de atacantes externos. Este trabajo aborda este problema, denominado problema α-separador, desde una perspectiva heurística, proponiendo un algoritmo basado en el Procedimiento de Búsqueda Adaptativa Aleatoria Greedy (GRASP). En particular, se propone un enfoque novedoso para el procedimiento constructivo, en el que se utilizan métricas de centralidad derivadas del análisis de redes sociales como criterio voraz. Además, se mejora la calidad de las soluciones proporcionadas mediante un método de combinación basado en Path Relinking (PR). Este trabajo explora diferentes variantes de PR, adaptando también la más reciente, Exterior PR, para el problema considerado. La combinación de GRASP + PR permite al algoritmo obtener soluciones de alta calidad en un tiempo de computación razonable. La propuesta se apoya en un conjunto de experimentos computacionales intensivos que muestran la calidad de la propuesta, comparándola con el algoritmo más competitivo encontrado en el estado del arte.
GRASP con Path Relinking para el problema del SumCut
(MAEB, 2012) Sánchez-Oro, Jesús; Duarte, Abraham
En este artículo se propone un algoritmo GRASP combinado con Path Relinking para resolver el problema de minimización del SumCut. En el problema del SumCut, a partir de un grafo de n nodos es necesario etiquetar todos los nodos de forma que ca- da uno de ellos reciba una etiqueta única del conjunto f1; 2;
Pruebas de evaluación de la asignatura Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio
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.
Variable neighborhood search approach with intensified shake for monitor placement
(Wiley, 2022) Casado, Alejandra; Mladenovíc, Nenad; Sánchez-Oro, Jesús; Duarte, Abraham
Several problems are emerging in the context of communication networks and mostof them must be solved in reduced computing time since they affect to critical tasks.In this research, the monitor placement problem is tackled. This problem tries tocover the communications of an entire network by locating a monitor in specificnodes of the network, in such a way that every link remains surveyed. In case thata solution cannot be generated in the allowed computing time, a penalty will beassumed for each link uncovered. The problem is addressed by considering the vari-able neighborhood search framework, proposing a novel constructive method, anintelligent local search to optimize the improvement phase, and an intensified shaketo guide the search to more promising solutions. The proposed algorithm is com-pared with a hybrid search evolutionary algorithm over a set of instances derivedfrom real-life networks to prove its performance.
Variable Neighborhood Search for the Vertex Separation Problem
(Elsevier, 2012) Duarte, Abraham; Escudero, Laureano F.; Martí, Rafael; Mladenovic, Nenad; Pantrigo, Juan José; Sánchez-Oro, Jesús
The vertex separation problem belongs to a family of optimization problems in which the objective is to nd the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI, computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for speci c types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the vertex separation problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to nd high-quality solutions with a moderate computing time for large-scale instances.
Videopíldoras de Algoritmos para Juegos
(2023) Sánchez-Oro, Jesús; Pantrigo, Juan José; Duarte, Abraham; Pérez, Sergio