Resumen
The Cyclic Min-Max Sitting Arrangement (CMMSA) is a graph layout optimization problem where the vertices of an input signed graph must be assigned to those of a cyclic host graph in a one-to-one correspondence. The input graph contains weighted edges, $+1$ or $-1$, representing positive and negative relationships between the vertices. For each vertex, a penalty occurs when an adjacent vertex connected by a negative-labeled edge is positioned closer in the cycle than any other adjacent vertex connected by a positive-labeled edge. The goal is to minimize the maximum number of such penalties occurring at any single vertex. This paper presents a comprehensive study based on the Variable Neighborhood Search (VNS) methodology for solving the CMMSA. Building upon successful applications of VNS in related problems, we analyze multiple algorithmic variants and strategies. Specifically, our investigation focuses on Variable Formulation Search (VFS), which defines multiple formulations for the problem, allowing it to further explore the solution space. We propose a total of four alternative formulations specially suited for this problem. The use of VFS within the VNS methodology outperforms the use of a default VNS schema, obtaining a better solution in 19 out of 20 instances considered in the study.
Marcos Robles
Estudiante de Doctorado en Inteligencia Artificial
Marcos Robles se graduó en Ingeniería del Software por la Universidad Rey Juan Carlos en 2022. Trabaja aquí como investigador predoctoral centrado en problemas de embebido de grafos.
Sergio Cavero
Doctor en Inteligencia Artificial
Sergio Cavero nació en Madrid (España) el 24 de septiembre de 1997. Se graduó en Ingeniería del Software por la Universidad Politécnica de Madrid en 2019. Durante sus estudios de grado realizó una estancia en la Universidad de Bradford (Reino Unido). Además, fue galardonado en dos ocasiones con la Beca de Excelencia de la Comunidad de Madrid, así como con el premio al Mejor Proyecto Fin de Carrera. Posteriormente, realizó un Máster en Inteligencia Artificial en la misma universidad (UPM) obteniendo los premios al Mejor Expediente Académico (‘Premio José Cuena’) y al Mejor Trabajo Fin de Máster. Sus resultados académicos le permitieron ser beneficiario de una de las ‘Ayudas para la Formación de Profesorado Universitario (FPU)’, financiadas por el Gobierno español. Actualmente realiza su tesis doctoral en la Universidad Rey Juan Carlos, dirigida por los profesores Abraham Duarte y Eduardo G. Pardo. Sus principales intereses de investigación se centran en la interfaz entre las Ciencias de la Computación, la Inteligencia Artificial y la Investigación Operativa. La mayoría de sus publicaciones tratan sobre el desarrollo de procedimientos metaheurísticos para problemas de optimización modelados por grafos.