Programación Entera Estocástica — Optimización de Decisiones Discretas Bajo Incertidumbre
- Propuesto por
- Dantzig, G. B.; Beale, E. M. L.
- Año
- 1955
- Tipo
- Optimization under uncertainty with discrete decisions
- Familia
- Simulation / optimization
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La Programación Entera Estocástica (SIP, por sus siglas en inglés) es un marco de optimización que combina variables de decisión enteras (discretas) con modelado probabilístico explícito de la incertidumbre.
Busca la mejor decisión aquí y ahora que minimice el costo esperado (o maximice el beneficio esperado) en una distribución de escenarios futuros, teniendo en cuenta que algunas decisiones deben tomarse antes de que se resuelva la incertidumbre.
La intuición detrás del método
Muchas decisiones reales son tanto discretas (construir una instalación o no; asignar un trabajador o no) como inciertas (la demanda, los costos y las restricciones no se conocen en el momento de la decisión). SIP maneja ambos desafíos simultáneamente. Modela el futuro incierto como un conjunto de escenarios con probabilidades asociadas, y luego encuentra la solución entera que se desempeña mejor en promedio, o que se protege contra los peores resultados. A diferencia de la programación lineal estocástica, la estructura discreta hace que el problema sea combinatoriamente más difícil, pero las decisiones producidas son directamente implementables sin redondeo ni aproximación.
Historia
La programación estocástica se remonta a Dantzig (1955) y Beale (1955), quienes propusieron independientemente modelos de recurso de dos etapas para programas lineales bajo incertidumbre. La extensión entera surgió a medida que la programación entera maduró en las décadas de 1960-1980. El libro de texto de Birge y Louveaux de 1997 codificó el campo, y Kleywegt et al. (2002) establecieron la Aproximación Promedio de Muestras como el enfoque computacional estándar para la optimización discreta estocástica a gran escala.
Cuándo usarlo
Utilizar Programación Entera Estocástica cuando las decisiones son inherentemente discretas (elecciones binarias, asignaciones de unidades completas, asignaciones de rutas) y los parámetros clave son inciertos en el momento de la decisión. Es adecuada para la planificación de capacidad, el diseño de redes de cadena de suministro, la programación bajo incertidumbre de demanda, el despacho de energía y la asignación de recursos con rendimientos aleatorios. NO la utilizar cuando todas las variables son continuas (la programación lineal estocástica es suficiente), cuando la incertidumbre es insignificante o totalmente observable antes de decidir, cuando la escala del problema hace que la enumeración de escenarios sea computacionalmente intratable sin infraestructura de descomposición, o cuando solo es relevante un único escenario determinista.
Limitaciones y consideraciones
- La complejidad computacional crece rápidamente con el número de escenarios y variables enteras; las instancias grandes son NP-hard.
- La generación de escenarios requiere distribuciones de probabilidad creíbles, que pueden ser difíciles de obtener o estimar a partir de datos limitados.
- Las extensiones multietapa (más de dos etapas) enfrentan un crecimiento exponencial en los árboles de escenarios y rara vez son tratables más allá de tres etapas.
- Se requiere habilidad de modelado para especificar correctamente la factibilidad del recurso, las restricciones de no anticipación y las estructuras de penalización.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Modela explícitamente la incertidumbre en lugar de usar estimaciones puntuales, produciendo soluciones que son robustas a los escenarios realizados.
- Maneja decisiones discretas y binarias de forma nativa, por lo que las soluciones son directamente implementables sin redondeo post-hoc.
- El marco de dos etapas separa claramente las decisiones estratégicas de primera etapa de las acciones operativas de recurso de segunda etapa.
- Soporta estructuras de recurso ricas que incluyen adquisición de recursos, costos de penalización y programación correctiva.
- Los límites de calidad estadísticos (vía SAA) permiten a los profesionales certificar la cuasi-optimalidad con confianza cuantificada.
Aplicaciones
- Diseño de redes de cadena de suministro bajo demanda y plazos de entrega estocásticos
- Planificación de la expansión de la generación de energía con producción renovable incierta
- Programación de quirófanos de hospital bajo duraciones variables de procedimientos
- Programación de tripulaciones de aerolíneas con retrasos de vuelo estocásticos
- Pre-posicionamiento de suministros de ayuda en logística humanitaria antes de desastres
- Optimización de carteras financieras con selección discreta de activos y rendimientos basados en escenarios
Cómo funciona
Cómo funciona
Formular el problema de primera etapa: elegir variables de decisión enteras (o mixtas enteras) x antes de que se revele la incertidumbre. Definir un objetivo que incluya tanto el costo inmediato como el costo esperado de recurso en todos los escenarios. Las restricciones que vinculan x con las condiciones de factibilidad se especifican aquí.
Fórmula
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]Representar la incertidumbre a través de un conjunto finito de escenarios. Cada escenario asigna valores específicos a parámetros aleatorios (niveles de demanda, costos, disponibilidad de recursos). Los escenarios pueden generarse mediante muestreo histórico, extracciones de Monte Carlo de distribuciones ajustadas o casos representativos definidos por expertos. Cada escenario tiene un peso de probabilidad que suma uno.
En la formulación estándar de dos etapas, después de fijar x y de que se realice el escenario xi, un problema de recurso (segunda etapa) determina las acciones correctivas y. El problema de recurso es a menudo un programa lineal o entero. El modelo completo minimiza c^T x más el costo esperado de recurso E[Q(x, xi)].
Fórmula
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xResolver los subproblemas de escenario para evaluar el costo de recurso de cada escenario dado x. Las técnicas incluyen branch-and-bound, descomposición de Benders, relajación Lagrangiana y el método de Aproximación Promedio de Muestras (SAA). Para árboles de escenarios grandes, los algoritmos de descomposición explotan la estructura de bloques entre escenarios.
Agregar los resultados de los subproblemas para estimar el costo esperado de recurso. En SAA, este es el promedio sobre S escenarios muestreados. La aproximación resultante converge a la expectativa verdadera a medida que S crece. Se pueden calcular límites estadísticos sobre la calidad de la solución a partir de la varianza de la muestra.
Fórmula
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)Verificar la optimalidad o cuasi-optimalidad mediante brechas de optimalidad, criterios de convergencia o intervalos de confianza estadísticos de SAA. Si la brecha no es aceptable, refinar el conjunto de escenarios, aumentar el tamaño de la muestra o ajustar las relajaciones. Informar la solución de primera etapa x* y su costo total esperado.
Errores comunes
- Usar muy pocos escenarios produce soluciones demasiado confiadas; usar demasiados hace que el problema sea computacionalmente infactible — equilibrar mediante diagnósticos de convergencia SAA.
- Ignorar la integralidad en la segunda etapa cuando en realidad es requerida conduce a estimaciones de costos optimistas y acciones de recurso infactibles.
- Asumir independencia de escenarios cuando los parámetros están correlacionados (por ejemplo, demanda y precio correlacionados) introduce un sesgo sistemático en la estimación del costo esperado.
- Olvidar las restricciones de no anticipación en problemas multietapa permite al modelo explotar información futura que no estaría disponible en la práctica.
Preguntas frecuentes
¿En qué se diferencia la Programación Entera Estocástica de la optimización robusta?
SIP minimiza el costo esperado en un conjunto de escenarios ponderado por probabilidad, aceptando que algunos escenarios pueden generar un alto costo si son poco probables. La optimización robusta minimiza el costo del peor caso en un conjunto de incertidumbre, sin hacer suposiciones probabilísticas. SIP requiere una distribución de probabilidad; la optimización robusta solo requiere un conjunto de incertidumbre. SIP es generalmente menos conservador pero requiere más datos.
¿Cuántos escenarios se necesitan en la práctica?
Esto depende de la dimensión del problema y la precisión deseada. El enfoque de Aproximación Promedio de Muestras (SAA) proporciona intervalos de confianza estadísticos sobre la brecha de optimalidad. Los estudios aplicados típicos utilizan docenas a miles de escenarios; los diagnósticos de convergencia (varianza del estimador del límite) guían la elección. Para problemas estructurados, las técnicas de reducción de escenarios (por ejemplo, Heitsch-Romisch) pueden reducir sustancialmente el número de escenarios.
¿Puede la Programación Entera Estocástica manejar más de dos etapas?
Sí, pero la SIP multietapa es significativamente más difícil. El árbol de escenarios crece exponencialmente con las etapas, y las restricciones de no anticipación deben aplicarse en cada nodo. En la práctica, los modelos de tres etapas son la norma para aplicaciones tratables; más allá de eso, generalmente se requieren aproximaciones como el horizonte rodante o la reducción del árbol de escenarios.
¿Qué software puede resolver modelos de Programación Entera Estocástica?
Los solucionadores comunes incluyen CPLEX y Gurobi (a través de lenguajes de modelado algebraico como AMPL, JuMP en Julia, o PuLP/Pyomo en Python), que soportan la descomposición de escenarios. Los marcos especializados de programación estocástica incluyen PySP (Python), solucionadores en formato SMPS y el paquete Julia StochasticPrograms.jl, que implementa SAA y la estrategia de "progressive hedging".
¿Es la Programación Entera Estocástica lo mismo que la Programación Mixta Entera Estocástica?
La Programación Entera Estocástica es la clase más amplia; la Programación Mixta Entera Estocástica (SMIP) se refiere específicamente a modelos donde algunas variables son continuas y otras son enteras en una o ambas etapas. SMIP es la forma más general y más frecuente en la práctica.
Métodos relacionados
Fuentes
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 978-1-4614-0237-4Copiado.Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
Abrir referencia DOICopiado.