A Variable Formulation Search Approach for Three Graph Layout Problems

Abstract

This paper studies the relationship between three linear layout problems: minimum linear arrangement, cutwidth minimization, and bandwidth minimization. Our research suggests that, given their correlation, optimizing one problem could optimize the others. The Variable Neighborhood Search metaheuristic can take advantage of this, especially by switching problem formulations during the search process. The paper presents experiments analyzing different strategies and provides insights about their effectiveness. Our findings indicate that the proposed variant of Variable Neighborhood Search outperforms traditional single-process optimization methods in terms of both solution quality and computational efficiency.

Publication
Lecture Notes in Computer Science
Sergio Cavero
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.

J. Manuel Colmenar
J. Manuel Colmenar
Associate Professor

My research interests are focused on metaheuristics applied to optimization problems. I have worked on different combinatorial optimization problems applying trajectorial algorithms such us GRASP or VNS. Besides, I am very interested in applications of Grammatical Evolution, specifically in model and prediction domain, as alternative to machine learning approaches.