La optimización en línea es un campo de la teoría de la optimización , más popular en la ciencia informática y la investigación de operaciones , que se ocupa de problemas de optimización que no tienen conocimiento o que tienen un conocimiento incompleto del futuro (en línea). Este tipo de problemas se denominan problemas en línea y se consideran 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 basadas en una entrada pieza por pieza y aquellos en los que una decisión se toma solo una vez. Un famoso problema en línea donde una decisión se toma solo una vez es el problema del alquiler de esquíes . En general, el resultado de un algoritmo en línea se compara con la solución de un algoritmo fuera de línea correspondiente que necesariamente es 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 .
Un problema que ejemplifica los conceptos de los 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 ha sido eliminado ( falló ) solo se revela al viajero cuando alcanza uno de los puntos finales del borde. El peor caso para este problema es simplemente que todos los bordes no confiables fallen y el problema se reduce al problema habitual del camino más corto . 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 es PSPACE-completo .
Hay muchos problemas formales que ofrecen más de un algoritmo en línea como solución: