Examinando por Autor "Cavero, Sergio"

Mostrando 1 - 12 de 12

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.
A Practical Methodology for Reproducible Experimentation: An Application to the Double-Row Facility Layout Problem
(MIT Press Direct, 2023) Martin-Santamaria, Raul; Cavero, Sergio; Herran, Alberto; Duarte, Abraham; Colmenar, Jose Manuel
Reproducibility of experiments is a complex task in stochastic methods such as evolu- tionary algorithms or metaheuristics in general. Many works from the literature give general guidelines to favor reproducibility. However, none of them provide both a practical set of steps and also software tools to help on this process. In this paper, we propose a practical methodology to favor reproducibility in optimization prob- lems tackled with stochastic methods. This methodology is divided into three main steps, where the researcher is assisted by software tools which implement state-of-the- art techniques related to this process. The methodology has been applied to study the Double Row Facility Layout Problem, where we propose a new algorithm able to obtain better results than the state-of-the-art methods. To this aim, we have also repli- cated the previous methods in order to complete the study with a new set of larger instances. All the produced artifacts related to the methodology and the study of the target problem are available in Zenodo.
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.
Actividades para la enseñanza de la robótica con el fin de mejorar el pensamiento computacional para estudiantes del Grado en Educación Infantil y en Educación Primaria
(2024-09-30) Cavero, Sergio; Hijón-Neira, Raquel; Borrás-Gené, Oriol; Pizarro, Celeste
Efficient Iterated Greedy for the Two-Dimensional Bandwidth Minimization Problem
(Elsevier, 2022) Cavero, Sergio; G. Pardo, Eduardo; Duarte, Abraham
Graph layout problems are a family of combinatorial optimization problems that consist of finding an embedding of the vertices of an input graph into a host graph such that an objective function is optimized. Within this family of problems falls the so-called Two-Dimensional Bandwidth Minimization Problem (2DBMP). The 2DBMP aims to minimize the maximum distance between each pair of adjacent vertices of the input graph when it is embedded into a grid host graph. In this paper, we present an efficient heuristic algorithm based on the Iterated Greedy (IG) framework hybridized with a new local search strategy to tackle the 2DBMP. Particularly, we propose different designs for the main IG procedures (i.e., construction, destruction, and reconstruction) based on the trade-off between intensification and diversification. Additionally, the improvement method incorporates three advanced strategies: an efficient way to evaluate the objective function of neighbor solutions, a tiebreak criterion to deal with “flat landscapes”, and a neighborhood reduction technique. Extensive experimentation was carried out to assess the IG performance over state-of-the-art methods, emerging our approach as the most competitive algorithm. Specifically, IG finds the best solutions for all instances considered in considerably less execution time. Statistical tests corroborate the merit of our proposal.
Evaluación del rendimiento de técnicas heurísticas para el S-labeling
(2024-06-19) Robles, Marcos; Cavero, Sergio; G. Pardo, Eduardo
El problema de S-labeling es un problema de etiquetado de grafos que asigna etiquetas numéricas a los vértices de un grafo, con el objetivo de minimizar una función objetivo. Concretamente, para cada par de vértices adyacentes se anota la etiqueta más pequeña del par. Una vez que se han revisado todos los pares, la función objetivo se calcula como la suma de todas las etiquetas anotadas. En este trabajo preliminar se realiza una propuesta que utiliza la metaheurística GRASP. Concretamente, se analizan un total de cuatro métodos constructivos aleatorizados, dos de ellos tomados de la literatura y dos de esta propuesta. Como método de mejora se proponen dos búsquedas locales y el uso de VND para combinarlas. El mejor algoritmo propuesto se compara con el mejor algoritmo del estado del arte (PIG), utilizando un conjunto de instancias de referencia. Los resultados muestran que uno de los métodos constructivos presentados es capaz de obtener soluciones competitivas con una desviación baja. También se comprueba que la fase de mejora es capaz de refinar las soluciones propuestas por el constructivo, obteniendo soluciones similares a las que se consiguen utilizando el algoritmo del estado del arte. Finalmente, se discuten los puntos fuertes y débiles de esta propuesta y se sugieren algunas líneas de investigación futuras.
Improving Learning Outcomes by Labeling Slides Based on the Complexity of Their Content
(IATED, 2024) Ortega Del Campo, David; Ruiz Parrado, Victoria; González de Lena, María T.; Cavero, Sergio; Vélez, José
Often, university professors tend to create slides that blend introductory, intermediate, and advanced content. The introductory content is necessary to understand the intermediate, and the intermediate is in turn necessary to comprehend the advanced. However, typically, it is left to the students to decide which part of the material is basic, which is intermediate, and which is advanced. However, many times, the professor doesn't even consider the possibility of addressing those advanced topics, but doesn't want to remove such material because a few students who are more advanced might benefit from it. Furthermore, the professor even loses a lot of class time explaining material that few students are prepared to understand, as they are still grasping the most basic concepts. This article analyzes the outcome of labeling each slide in a university-level Object-Oriented Programming course with tags such as introductory, intermediate, or advanced. These results are comparatively analyzed with other outcomes obtained in other courses taken by the same students, where the slides have not been labeled.
Un marco general para el diseño de heurísticas constructivas para problemas de embebidos de grafos
(XX Conferencia de la Asociación Española para la Inteligencia Artificial (CAEPIA 24), 2024-06-19) Cavero, Sergio; G. Pardo, Eduardo; Resende, Mauricio G. C.
Los problemas de embebido de grafos (GLP, por sus siglas en inglés, Graph Layout Problems) son una familia de problemas de optimización combinatoria que buscan asignar los vértices de un grafo de entrada a los vértices de un grafo huésped, satisfaciendo restricciones específicas y optimizando una función matemática. Debido a su complejidad computacional, se suelen utilizar algoritmos aproximados, como las heurísticas. Este artículo presenta una revisión de las heurísticas constructivas que se utilizan para generar soluciones de partida para algunos de los GLP más estudiados de la literatura. A partir de la revisión realizada, se propone un marco general para la propuesta de heurísticas constructivas para esta familia de problemas u otros problemas relacionados, así como un conjunto de posibles trabajos futuros.
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.
Wordle in the Classroom: a Game-changing Approach to Active Learning
(IATED, 2024) Cavero, Sergio; G. Pardo, Eduardo; María T., González de Lena
This work presents an innovative approach to engage student participation through active learning, using the popular online word-guessing game, named Wordle. Wordle is a word-guessing game where players have six attempts to guess a five-letter word. With each guess, the letters turn the background color to indicate correctness: green for correct letters in the right position, yellow for correct letters in the wrong position, and gray for incorrect letters. Players aim to deduce the mystery word using logic and word association within the given attempts, making it both challenging and rewarding. The method proposed here involves students through the challenge of solving a set of personalized Wordle puzzles, at the end of the class, which include key concepts studied on the previous lecture. In this case, the words might have a different length. Students compete in a Wordle league, that is active during the whole semester accumulating points for each word guessed, fostering competition and motivation. The standings of the league are publicly available for all students. In addition, students are asked, at the end of the course, to create a concept map with all the keywords found, following the Unified Modeling Language (UML) standard, which is a fundamental topic of the subject. This activity aids in consolidating acquired knowledge and developing synthesis and information organization skills. The proposal was validated in the academic year 2022/2023, in the Engineering of Requirements (ER) course, which is a subject within the Software Engineering degree at Universidad Rey Juan Carlos (Madrid, Spain). The results showed a positive correlation between Wordle participation and academic performance. Furthermore, they suggested that students who actively engaged in the activity demonstrated a greater commitment to the subject and a better understanding of the key concepts. The benefits of this active learning proposal are manifold. It encourages class attendance, improves attention in class, and increases students’ motivation. It also aids in consolidating acquired knowledge and developing synthesis and information organization skills. Further research is needed to understand the impact of this strategy, but preliminary results are encouraging and suggest a promising path towards innovation in digital education.