Abstract
Optimization is a discipline that addresses the search for the best possible solution, called the optimal solution, to a problem mathematically modeled. These problems can be classified according to its computational complexity. Problems belonging to the NP-hard class are too complex to be solved with an exact algorithm in a reasonable amount of time. Alternatively, these problems can be approached through approximate techniques that allow finding good quality solutions, although not necessarily optimal, in a reasonable amount of computing time. Among these techniques, heuristic and metaheuristic algorithms stand out, since they have been proven as useful tools in solving high-complexity real problems. In this Doctoral Thesis, heuristic and metaheuristic algorithms are proposed for the resolution of four Graph Layout Problems (GLP). Specifically, the problems studied belong to the NP-hard class and can be framed as combinatorial optimization problems. GLPs aim to find the best possible assignment of the vertices of an input graph to the vertices of a host graph, optimizing a certain objective function. More specifically, this Doctoral Thesis focuses on the study of GLPs in which the embedding is done in circular layouts. This family of problems is of great interest due to the variety of practical applications they have. In this research, a methodology for addressing GLPs is proposed. Specifically, it starts from the study of each problem, and then proposes heuristic and metaheuristic algorithms for tackling the problem. After a preliminary experimentation, the algorithmic proposal is compared to the existing methods in the state of the art. This methodology has been successfully applied to the studied problems, resulting in various scientific publications that compile the main findings of the research carried out.
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.