La optimización en línea es un campo de la teoría de la optimización , más popular en la ciencia de la computación y la investigación de operaciones , que se ocupa de los problemas de optimización que tienen un conocimiento incompleto o nulo del futuro (en línea). Este tipo de problemas se denominan problemas en línea y se ven como opuestos a los problemas de optimización clásicos donde se asume información completa (fuera de línea). La investigación sobre la optimización en línea se puede distinguir en problemas en línea donde se toman múltiples decisiones secuencialmente basándose en una entrada de pieza por pieza y aquellos en los que una decisión se toma solo una vez. Un problema en línea famoso en el que se toma una decisión solo una vez es el problema del alquiler de esquís . En general, la salida de un algoritmo en línea se compara con la solución de un algoritmo fuera de línea correspondiente que es necesariamente siempre óptimo y conoce toda la entrada de antemano (análisis competitivo).
En muchas situaciones, las decisiones presentes (por ejemplo, la asignación de recursos) deben tomarse con un conocimiento incompleto del futuro o los supuestos distributivos sobre el futuro no son confiables. En tales casos, se puede utilizar la optimización en línea [1] , que es diferente de otros enfoques como la optimización robusta , la optimización estocástica y los procesos de decisión de Markov.
Problemas en línea
Un problema que ejemplifica los conceptos de algoritmos en línea es el problema del viajero canadiense . El objetivo de este problema es minimizar el costo de alcanzar un objetivo en un gráfico ponderado donde algunos de los bordes no son confiables y pueden haber sido eliminados del gráfico. Sin embargo, que un borde se ha eliminado ( fallido ) solo se revela al viajero cuando alcanza uno de los puntos finales del borde. El peor de los casos para este problema es simplemente que todos los bordes no confiables fallan y el problema se reduce al problema habitual de la ruta más corta . Se puede realizar un análisis alternativo del problema con la ayuda del análisis competitivo. Para este método de análisis, el algoritmo fuera de línea sabe de antemano qué bordes fallarán y el objetivo es minimizar la relación entre el rendimiento de los algoritmos en línea y fuera de línea. Este problema está completo en PSPACE .
Hay muchos problemas formales que ofrecen más de un algoritmo en línea como solución:
Referencias
- ^ Jaillet, Patrick y Michael R. Wagner. Optimización online. Springer Publishing Company, Incorporated, 2012.
- ^ Dochow, Robert (2016). Algoritmos online para el problema de selección de carteras . Springer Gabler.