Resumen del trabajo fin de master



Título: Aprendizaje dinámico de selección de variable en un algoritmo de ramificación y acotación
Universidad que ofrece el proyecto: Universidade de Santiago de Compostela
Director/a:
Pateiro López, Beatriz;  González Rodríguez, Brais
Alumno/a:
Riveiro Rojo, Cintia
Resumen:
Los algoritmos de ramificación y acotación son una de las técnicas más utilizadas a la hora de resolver problemas de optimización. Dicha técnica se basa en resolver relajaciones del problema original, cuya resolución es más sencilla que la del problema original. Durante el desarrollo del algoritmo, hay que tomar diversas decisiones sobre el proceso de ramificación. En particular, este trabajo se centrará en cómo elegir la variable de ramificación en cada una de las iteraciones del algoritmo, eligiendo para ello entre diferentes criterios de ramificación. Hasta ahora, se ha estudiado la incorporación de técnicas de aprendizaje automático en este contexto, con el objetivo de seleccionar el mejor criterio de ramificación para la resolución de un determinado problema de optimización. Sin embargo, este procedimiento nos lleva a resolver un problema concreto utilizando siempre el mismo criterio de ramificación en todos los nodos del avance del algoritmo. El objetivo de este trabajo es refinar esta técnica, proponiendo un método de aprendizaje dinámico (aprendizaje online), de forma que, en lugar de fijar un único criterio para cada problema, podamos ir seleccionando el mejor criterio de ramificación a medida que crece el árbol, lo que podría derivar en un mejor rendimiento del proceso de aprendizaje y de la resolución del problema, pues se tendrá en cuenta información adicional en cada iteración del algoritmo de ramificación y acotación.
Más información