Abstract
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
Artificial Intelligence Phd Student
Marcos Robles graduated in Software Engineering from the Rey Juan Carlos University in 2022. He is working here as a predoctoral researcher focusing in Graph Layout Problems.
Sergio Cavero
Phd in Artificial Intelligence
Sergio Cavero was born Madrid (Spain) on September 24, 1997. He graduated in Software Engineering from Universidad Politécnica de Madrid in 2019. During his undergraduate studies he made a stay at the University of Bradford (UK). In addition, he was awarded twice with the ‘Beca de Excelencia of the Comunidad de Madrid, and also awarded for the Best Final Degree Project. Later, he completed a Master’s Degree in Artificial Intelligence at the same university (UPM) obtaining awards for Best Academic Record (‘Premio José Cuena’) and Best Master’s Thesis. He academic results lend him be beneficiary of one of the ‘Ayudas Para la Formación de Profesorado Universitario (FPU)’, funded by the Spanish Government. He is currently carrying out his doctoral thesis at the Universidad Rey Juan Carlos, supervised by Professors Abraham Duarte and Eduardo G. Pardo. His main research interests focus on the interface among Computer Science, Artificial Intelligence and Operations Research. Most of his publications deal with the development of metaheuristics procedures for optimization problems modeled by graphs.