Optimizacion robusta: analisis y comparacion de metodos aplicados a problemas de camino mas corto

Abstract

La presente memoria aborda los problemas de optimización robusta, y específicamente los problemas de camino más corto (CMC) con incertidumbre intervalar asociada a los costos. En los últimos años se han realizado una gran cantidad de estudios en optimización robusta, destacando dos vertientes principales de estudio: Minimax Regret y la de Bertsimas & Sim. El modelo del Minimax Regret busca encontrar la solución que posea la mejor peor desviación robusta (en términos del ‘regret’ o ‘arrepentimiento’ por seleccionar una solución que es sub-optimal pero que posee cierta robustez) frente a todos los escenarios y caminos posibles. Mientras el método de Bertsimas & Sim plantea un modelo que en su contraparte robusta conserva la linealidad del problema de origen, y que además permite regular la robustez del modelo frente al conservatismo de la solución encontrada a través de un parámetro. Con el propósito de realizar un análisis y comparación de los métodos en estudio, se aplican los diferentes modelos a problemas de camino más corto para dos clases de grafos conocidos para experimentación: Karasan y Aleatorios. Se da solución al problema de Minimax regret a través de un algoritmo de aproximación (K&Z), y por medio de un modelo de programación lineal entera que resuelve el problema exacto a través del solver comercial CPLEX. Además se da solución al modelo de Bertsimas & Sim (B&S) resolviendo 1 A  problemas de camino más corto mediante un programa especialmente desarrollado, donde A es el conjunto de vértices de la red en estudio. De esta manera, se realiza el análisis y comparación de los métodos resolviendo una gran variedad y cantidad de problemas, y se establece una relación entre las soluciones obtenidas por cada método.