A Variable Neighborhood Search Approach for the S-labeling Problem

Resumen

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

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.