Abstract
The S-labeling problem is a graph layout problem that assigns numeric labels to the vertices of a graph. It aims to minimize the sum of the minimum numeric label assigned to each pair of adjacent vertices. In this preliminary work, we propose the use of the Variable Neighborhood Search (VNS) framework to test different Shake procedures and Local Search methods for the problem. We compare our VNS variants with the state-of-the-art Population-based Iterated Greedy algorithm on a set of benchmark instances. The results show that our VNS methods can obtain competitive solutions with a low deviation, but they are not able to improve the best-known values. We discuss the strengths and weaknesses of our proposal and suggest some future research directions. This work lays the groundwork for future research into the S-Labeling problem using Variable Neighborhood Search.
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.