En mi primera publicación de TDS, escribí sobre cómo traducir un problema del mundo real a un programa lineal entero. En el segundo, escribí sobre cómo hacer que ese programa sea sólido frente a la incertidumbre. Ambas eran variaciones de la misma idea: tomar una pregunta confusa del mundo real, incluirla en un LP y dejar que un solucionador haga el resto.
Sin embargo, hay un momento en la vida de todo optimizador en el que el LP comienza a sentirse demasiado ordenado. La demanda es un número. El tiempo de viaje es un número. La velocidad del viento es un número. El modelo acepta la entrada, devuelve una solución óptima y continúa su camino. La realidad que se suponía que describían esos números (desordenada, nerviosa y ocasionalmente sorprendente) en realidad no aparece en ninguna parte.
La programación estocástica es el campo que toma en serio esa incomodidad. En lugar de pretender que los datos son exactos, incorpora la incertidumbre directamente en el modelo. El precio que pagas es un poco más de notación; la recompensa son decisiones que se mantienen cuando el mundo no coopera.
Esta publicación es un recorrido suave por los conceptos básicos. Veremos por qué el enfoque obvio no funciona, repasaremos las cuatro formas estándar de manejar la incertidumbre en un programa lineal y finalizaremos con una rápida comprobación de cordura para ver si algo de esto vale la pena el esfuerzo. Hay algunas matemáticas, pero son las mismas que ya conoces de LP, con un símbolo adicional adjunto.
Punto de partida: una empresa de moda con una mala bola de cristal
Para concretar esto, usaremos el ejemplo de ejecución del dr. Conferencias de Ruben van Beesten (más sobre eso en los créditos a continuación). Es así.
Diriges una empresa de moda que vende ropa de invierno en Alemania. La producción se realiza en Bangladesh, que es barato pero lento: los productos tardan algunas semanas en llegar. Entonces, en otoño, debes decidir cuánto producir para la próxima temporada de invierno.
Esto puede salir mal de dos maneras: si produce muy poco, perderá ventas; Si produce demasiado, se quedará con existencias que no podrá vender. Toda la pregunta es cuánto producir ahora, y la respuesta depende de algo que aún no se sabe: la demanda invernal.
Si ignoraras la incertidumbre por un momento y fingieras que la demanda era un número fijo, podrías escribir un LP básico:
Aquí x es cuánto se produce, c es el costo unitario de producción, h es la demanda y T es simplemente la matriz de identidad (una unidad producida satisface una unidad de demanda). La restricción dice: producir al menos tanto como se demanda.
Esto está bien si realmente se conoce h. El problema es que la demanda no es un número, es una variable aleatoria. Llamémoslo ξ. La versión honesta del modelo se vería así:
Y aquí nos topamos con una pared. ¿Qué significa que x satisfaga una restricción que depende de una variable aleatoria? ¿Es x = 100 factible si la demanda podría ser 80, podría ser 120 y podría estar en algún punto intermedio? El problema no es difícil de resolver: está mal definido. El solucionador ni siquiera sabe qué problema le estás pidiendo que resuelva.
La programación estocástica es, en esencia, una colección de respuestas basadas en principios a esa pregunta. Veremos los cuatro más comunes.
Cuatro formas de manejar la incertidumbre
Cada uno de los cuatro enfoques toma el PL mal definido anterior y lo convierte en un problema de optimización bien definido. Difieren en lo que suponen que usted sabe acerca de la incertidumbre y en cuán cautelosos son ante los malos resultados.
1. Optimización sólida: prepárese para lo peor
El enfoque más cauteloso. No es necesario conocer la distribución de probabilidad completa de ξ, sino sólo su soporte, es decir, el conjunto de valores que posiblemente podría tomar. A este conjunto lo llamamos conjunto de incertidumbre, escrito U. Entonces preguntas: ¿cuál es la mejor decisión que sigue siendo factible sin importar cuál ξ ∈ U aparezca realmente?
La restricción ahora debe cumplirse para cada ξ en el conjunto de incertidumbre. En nuestro ejemplo de moda con U = [0, 10], estarías planificando siempre una demanda de 10, el peor de los casos.
Ésa es la fortaleza y la debilidad de una optimización sólida en una frase. La solución es a prueba de balas, pero también es conservadora: a menudo tendrá que quedarse con un inventario que no necesitaba, porque planeó como si el peor de los casos estuviera garantizado. Si leyó mi publicación anterior sobre cómo fortalecer los programas lineales, este es exactamente el marco que se encuentra detrás de esos cuatro pasos.
2. Restricciones de probabilidad: relajar el peor de los casos
Planes de optimización sólidos para cualquier resultado posible. Las limitaciones del azar lo relajan para: planificar para la mayoría de ellos. Se elige un nivel de probabilidad α, digamos 95%, y se requiere que la restricción se cumpla con al menos esa probabilidad:
Esto se llama restricción de probabilidad conjunta: todas las entradas del vector de restricción deben satisfacerse simultáneamente, con probabilidad conjunta ≥ α. Una variante más débil trata cada fila por separado:
Estas son restricciones de probabilidad individuales: cada restricción i debo cumplir con una probabilidad de al menos αᵢ, pero no te importa el evento conjunto. Ejercicio rápido: si igualas cada αᵢ a la articulación α, ¿qué formulación es más conservadora?
Respuesta: la versión conjunta. Satisfacer todas las restricciones simultáneamente es un requisito más estricto que satisfacer cada una de forma aislada, por lo que la formulación conjunta tiene una región factible más pequeña y un costo óptimo peor (más alto). De cualquier manera, las restricciones de probabilidad le dan un mando, α, para determinar qué tan cauteloso quiere ser. Póngalo a 1 y volverá a ser (casi) robusto. Bájelo a 0,5 y básicamente estará lanzando una moneda al aire sobre la viabilidad. La mayoría de las aplicaciones reales se encuentran en algún lugar entre 0,9 y 0,99.
Hay un problema que vale la pena señalar: las restricciones al azar son difíciles en general. El término de probabilidad dentro de la restricción es una función de x no lineal y a menudo no convexa, por lo que generalmente no se puede entregar la formulación directamente a un solucionador LP estándar. Hay casos especiales tratables (ruido gaussiano, ciertas mezclas de distribuciones, aproximaciones basadas en muestras), pero el problema general es más difícil de lo que parece a primera vista.
3. Modelos de recurso en dos etapas: decidir, observar, corregir
Los dos primeros enfoques tratan la violación de restricciones como algo que se debe evitar, ya sea siempre (robusto) o con alta probabilidad (oportunidad). A veces ese es el marco equivocado. En nuestro ejemplo de moda, no satisfacer la demanda no es catastrófico. Es molesto. Normalmente se puede solucionar: producir un pequeño lote de emergencia en Alemania a un coste mayor, o enviarlo por vía aérea, o simplemente aceptar las ventas perdidas y seguir adelante.
Esta idea de que violar una restricción no es el fin del mundo y que se puede tomar una acción correctiva más adelante es el corazón de los modelos de recurso. En la versión de dos etapas, la línea de tiempo se ve así:
Etapa 1 (ahora): tomas una decisión de primera etapa x mientras ξ aún es incierta. Entonces: se realiza ξ, es decir, la variable aleatoria se convierte en un número conocido. Etapa 2 (posterior): tomas una decisión y en la segunda etapa, conociendo ξ.
Matemáticamente, la primera etapa parece casi un LP básico, excepto que el objetivo ahora contiene un costo futuro esperado:
La función v(ξ, x) es el valor óptimo del problema de la segunda etapa, dado que elegiste x en la primera etapa y que ξ resultó ser el valor realizado:
Lea esto atentamente. El lado derecho, h(ξ) − T(ξ) x, es el déficit, es decir, cuánto no cubrió su decisión de la primera etapa, después de que ξ fuera revelado. La decisión de recurso y cierra entonces esa brecha, a un costo q(ξ)ᵀ y. Entonces, la estructura es: pagar el costo inicial cᵀ x, y además pagar el costo esperado de limpieza después de que la variable aleatoria haga su trabajo.
Esa es toda la idea. Los modelos de recurso de dos etapas son, con diferencia, la formulación más común en la práctica, en parte porque capturan la cronología real de las decisiones en muchos problemas reales (planificación de la producción, inventario, despacho de energía, programación) y en parte porque se comportan matemáticamente relativamente bien.
Un par de fragmentos de vocabulario con los que te tropezarás si sigues leyendo:
Un modelo tiene recurso fijo si la matriz de recurso W no depende de ξ. Muchos algoritmos sólo funcionan en este caso. Un modelo tiene un recurso (relativamente) completo si siempre hay una decisión de recurso factible y, sin importar lo que resulte ser ξ y sin importar qué x elijas. Si el recurso completo falla, el problema de la segunda etapa puede resultar inviable, lo que se convierte en una restricción implícita en la primera etapa. (De aquí es exactamente de donde provienen los recortes de viabilidad de Benders, pero esa es una historia para otra publicación).
4. Modelos de recurso en varias etapas: seguir adelante
A veces la vida no consta de dos etapas. No se decide, se observa, se corrige una vez y se va a casa; decides, observas, decides, observas, decides,… una y otra vez. Los modelos de recurso en varias etapas son la extensión natural.
En nuestro ejemplo de moda, supongamos que ya no elegimos una vez en otoño, sino tres veces: en otoño (barato, en Bangladesh), a principios de invierno (más caro, en Rumania) y a finales del invierno (más caro, en Alemania). La demanda se revela gradualmente a lo largo de la temporada y en cada etapa decidimos en función de lo que hemos observado hasta ahora.
La notación se vuelve más pesada, terminas escribiendo funciones de valor recursivas Qₜ, con historias ξ[t] = (ξ₁,…, ξₜ) colgando de ellas, pero conceptualmente no sucede nada nuevo. Cada etapa es un problema de recurso anidado dentro de la anterior. La forma natural de imaginar esto es como un árbol de escenarios: cada nodo es un estado del mundo, cada rama es una posible realización de la siguiente variable aleatoria y un escenario es un camino completo de raíz a hoja.
Una sutileza. Un escenario es la trayectoria completa de ξ, no sólo una realización. Saber que ξ₂ = 10 no te dice en qué escenario te encuentras, porque ξ₃ aún no ha sucedido. Esto es importante cuando comienzas a escribir el equivalente determinista (siguiente sección), porque debes tener cuidado de que tus decisiones solo dependan de información que realmente haya sido observada en el momento en que se toma la decisión. Esa propiedad se llama no anticipatividad: no se puede anticipar el futuro. El modelo felizmente haría trampa si no lo aplicaras explícitamente.
¿Cómo solucionamos realmente un modelo de recurso?
Hasta ahora hemos estado escribiendo modelos. Para resolverlos, normalmente los transformamos en algo que un solucionador de LP estándar pueda analizar. El truco es la formulación equivalente determinista.
Supongamos que la variable aleatoria ξ tiene una distribución discreta: toma un número finito de valores ξ¹, ξ²,…, ξˢ (llamados escenarios), cada uno con probabilidad pₛ. Entonces el costo esperado de la segunda etapa es simplemente una suma finita, y podemos escribir todo el problema de dos etapas como un gran PL introduciendo una copia de y por escenario:
Es un LP normal. Grande, posiblemente muy grande, si tienes escenarios S, básicamente has copiado veces la segunda etapa S, pero es un LP. Puede entregárselo directamente a HiGHS, Gurobi, CPLEX o cualquier solucionador que desee y lo resolverá.
Siguen dos preguntas naturales.
Primero: ¿qué pasa si la distribución de ξ no es discreta? En ese caso, el equivalente determinista tiene infinitos escenarios y no es de dimensión finita. La solución estándar es la aproximación del promedio muestral: extraiga una muestra de tamaño S de la distribución verdadera, resuelva el equivalente determinista muestreado y deje que S crezca hasta que su solución se estabilice estadísticamente. Hay toda una literatura sobre qué tan grande debe ser S y qué garantías se obtienen.
Segundo: ¿qué pasa si el equivalente determinista es demasiado grande para resolverlo directamente? Aquí es donde entran los métodos de descomposición. La descomposición de Benders divide el problema en un problema maestro en las variables de la primera etapa y un subproblema por escenario, luego pasa información de forma iterativa entre ellos. Para modelos de múltiples etapas con muchas etapas, el truco análogo es la programación dinámica dual estocástica (SDDP), que utiliza funciones de muestreo y valor aproximado para evitar construir el árbol de escenarios completo. Ambos están lo suficientemente avanzados como para merecer sus propias publicaciones, así que volveré a ellos más adelante.
¿Vale la pena todo esto?
Pregunta honesta. Los programas estocásticos son más complicados de formular, más difíciles de resolver y más lentos de ejecutar que sus primos deterministas. Si su problema del mundo real no es muy sensible a la incertidumbre, sería mejor simplemente conectar la demanda esperada a un LP normal y dar por terminado el día.
La buena noticia es que puedes cuantificar exactamente cuánto te permite ganar con la formulación estocástica. Hay dos métricas clásicas y vale la pena conocer ambas.
Defina cuatro números:
En palabras: SP es el valor óptimo del programa estocástico real. EV es lo que se obtiene si se reemplaza ξ con su valor esperado y se resuelve el problema determinista resultante; llame a su solución x̄. EEV es el costo esperado de implementar esa solución determinista x̄ en el mundo estocástico real. Y WS ("esperar y ver") es el costo esperado si pudieras echar un vistazo al ξ realizado antes de decidir x, el mejor caso de trampa.
A partir de estos cuatro números puedes construir dos cantidades altamente informativas:
VSS es el valor de la solución estocástica: cuánto peor estaría si simplemente resolviera el problema determinista con valores promedio e implementara su solución. Si VSS es pequeño, el programa estocástico no le permitirá ganar mucho; el atajo determinista está bien.
EVPI es el valor esperado de la información perfecta: cuánto ganarías si un oráculo benevolente te entregara el ξ realizado antes de que tuvieras que decidir. Si el EVPI es pequeño, sus pronósticos ya contienen la mayor parte de la información que necesita; invertir en mejores predicciones probablemente no cambie la situación. Si el EVPI es grande, mejores datos tienen valor real.
Las dos métricas avanzan en una ordenada cadena de desigualdades (asumiendo incertidumbre solo en el lado derecho):
Léalo de izquierda a derecha: hacer trampa con la media (EV) es como mucho tan malo como hacer trampa con la realización (WS), que es como mucho tan malo como la respuesta estocástica honesta (SP), que es como mucho tan malo como conectar la solución determinista y vivir con ella (EEV). La cadena implica un límite superior libre en VSS que puedes calcular antes de resolver el SP: VSS ≤ EEV − EV. Si esa brecha es pequeña, el atajo determinista es suficientemente bueno y puede ahorrarse el dolor de cabeza.
A dónde ir desde aquí
Esta publicación se ciñó a lo básico: cómo escribir un programa estocástico. El siguiente paso natural es cómo resolver los grandes de manera eficiente. Los dos grandes caballos de batalla son:
Descomposición de Benders: para modelos de dos etapas, descompone el equivalente determinista en un problema maestro (en x) más un subproblema por escenario y los concilia con cortes. Particularmente elegante cuando tienes muchos escenarios pero una primera etapa relativamente pequeña. Programación dinámica dual estocástica (SDDP): para modelos de múltiples etapas, utiliza muestreo y aproximaciones lineales por partes de las funciones de valor futuro. Se utiliza famosamente en la programación de energía hidroeléctrica, donde el árbol de escenarios es tan grande que la enumeración explícita es inútil.
Ambos merecen sus propios puestos. Si hay interés, los escribiré.
Llevar
Si está utilizando LP en cualquier contexto donde los datos de entrada son realmente inciertos debido a la demanda prevista, el clima, los precios, los tiempos de viaje o cualquier otra cosa, entonces su modelo está tomando una decisión implícita sobre cómo manejar esa incertidumbre. "Simplemente usa el medio" es una elección. También lo es “planear para lo peor”. La programación estocástica le brinda el vocabulario para hacer explícita esa elección y las herramientas para evaluar si su elección fue buena (hola, VSS).
Para resumir las cuatro formas básicas de modelar la incertidumbre en un LP:
Optimización sólida: planifique para el peor de los casos en un conjunto de incertidumbre determinado. Restricciones de probabilidad: requieren viabilidad con al menos probabilidad α. Recurso en dos etapas: decidir, observar, corregir; pagar un costo de recurso esperado. Recurso en varias etapas: la misma idea, repetida a lo largo del tiempo en un árbol de escenarios.
Y dos métricas que vale la pena tener en su bolsillo: VSS (¿ayuda el modelo estocástico?) y EVPI (¿ayudarían mejores pronósticos?).
La mayoría de los problemas reales no son deterministas. La buena noticia es que tu kit de herramientas de modelado tampoco tiene por qué serlo.
Créditos y referencias
Esta publicación está basada en conferencias del dr. Ruben van Beesten (Universidad Noruega de Ciencia y Tecnología) de su curso sobre Programación Estocástica impartido en octubre de 2023, al que tuve el placer de asistir en Trondheim, Noruega. El ejemplo de la empresa de moda, la taxonomía de formulaciones de cuatro vías y el marco VSS/EVPI provienen directamente de sus diapositivas; cualquier torpeza en el recuento es mía.
El ejercicio de modelado original que motiva gran parte de la intuición del modelo de recurso proviene de
Higle, JL (2005). Programación estocástica: optimización cuando la incertidumbre importa. En INFORMS TutORials in Operations Research, págs. 30–53.
Un par de consejos más que vale la pena conocer:
Kleywegt, AJ, Shapiro, A. y Homem-de-Mello, T. (2002). El método de aproximación del promedio muestral para la optimización discreta estocástica. Revista SIAM sobre optimización, 12 (2), 479–502. La referencia estándar para SAA. Higle, JL y Sen, S. (1991). Descomposición estocástica: un algoritmo para programas lineales de dos etapas con recurso. Matemáticas de la investigación de operaciones, 16(3), 650–669. Uno de los pocos métodos que maneja distribuciones no discretas directamente.
Y, por supuesto, las dos publicaciones anteriores de esta serie: Cinco preguntas que le ayudarán a modelar mejor programas lineales enteros y Cuatro pasos para robustecer su programa lineal.