Título: Ramificación y acotación para la resolución de problemas de optimización polinómica
Universidad que ofrece el proyecto: Universidade de Santiago de Compostela
Director/a: González Díaz, Julio
Resumen:
A la hora de resolver problemas de optimización matemática no lineales y no convexos, las técnicas de resolución se dividen en dos grandes familias: algoritmos de optimalidad local y algoritmos de optimalidad global. Estos últimos suelen consistir en algoritmos de ramificación y acotación, donde la ramificación se conoce como “ramificación espacial”, para distinguirla de la ramificación subyacente a los algoritmos para la resolución de problemas de programación lineal y entera.
Este trabajo girará en torno a una implementación específica de estas técnicas de ramificación espacial, en el ámbito de la optimización polinómica. El optimizador en cuestión, RAPOSa (González-Rodríguez y otros, 2023), ha sido desarrollado por investigadores de la USC basándose en la técnica RLT introducida por Sherali y Tuncbilek (1992).
Tras una fase inicial de familiarización con RAPOSa y con la técnica RLT, el estudiante colaborará en el estudio y validación de posibles variaciones en el procedimiento de ramificación y acotación, con el objetivo de mejorar su eficiencia computacional.
Referencias:
• Sherali, H. D., & Tuncbilek, C. H. (1992). A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization, 2, 101-112.
• González-Rodríguez, B., Ossorio-Castillo, J., González-Díaz, J., González-Rueda, Á. M., Penas, D. R., & Rodríguez-Martínez, D. (2023). Computational advances in polynomial optimization: RAPOSa, a freely available global solver. Journal of Global Optimization, 85(3), 541-568.
| Más información |