Técnicas de aprendizaje estadístico en optimización polinómica

Abstract

La primera parte de este trabajo de fin de grado se centrará en introducir los conceptos matemáticos necesarios para comprender la experimentación realizada en el estudio computacional. En concreto, introduciremos la optimización polinómica y la técnica RLT (Reformulation- Linearization Tecnique en inglés). Este algoritmo, que permite resolver problemas de optimización no convexos mediante la generación de relajaciones lineales del problema original, está enmarcado dentro de un algoritmo de ramificación y acotación. También se introducirá el concepto de aprendizaje supervisado, una de las ramas fundamentales del aprendizaje estadístico, y algunos de los algoritmos más utilizados dentro de este campo, que formarán parte del proceso de experimentación. En la segunda parte del trabajo, se llevará a cabo un estudio computacional en el que se utilizarán diversas técnicas de aprendizaje supervisado para entrenar un modelo capaz de seleccionar la configuración del algoritmo RLT que mejor se adapte a la instancia que se esté evaluando.The first part of this work will focus on introducing the mathematical concepts necessary to understand the testing carried out in the computational study. Specifically, we will introduce polynomial optimization and the Reformulation-Linearization Tecnique (RLT). This algorithm, which allows solving non-convex optimization problems by generating linear relaxations of the original problem, is included in a branching and bounding algorithm. We will also introduce the concept of supervised learning, one of the fundamental branches of statistical learning, and some of the most widely used algorithms in this field, which will be part of the experimentation process. In the second part of the work, a computational study will be performed in which several supervised learning techniques will be used to train a model able to select the RLT algorithm configuration that best suits the instance under evaluation.