Programación Estocástica Entera Mixta — Optimización Bajo Incertidumbre con Decisiones Discretas y Continuas
- Propuesto por
- Birge, J. R.; Louveaux, F.; Sen, S.
- Año
- 1990s–2000s
- Tipo
- Stochastic optimization model
- 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 Estocástica Entera Mixta (SMIP, por sus siglas en inglés) es un marco de optimización que encuentra la mejor combinación de decisiones binarias, enteras y continuas cuando los parámetros clave —costos, demandas, capacidades— son inciertos y se modelan como distribuciones de probabilidad sobre un conjunto de escenarios.
Extiende la Programación Entera Mixta (MIP) clásica al incorporar árboles de escenarios u objetivos de valor esperado que se protegen contra la incertidumbre respetando las restricciones combinatorias.
La intuición detrás del método
Muchos problemas de planificación reales exigen elecciones de sí/no o de números enteros —construir una instalación o no, asignar un número entero de vehículos—, pero el futuro es incierto. La SMIP formaliza esto considerando una colección de escenarios futuros plausibles y eligiendo compromisos de primera etapa (antes de que se revele la incertidumbre) que minimizan el costo esperado o maximizan el beneficio esperado en todos los escenarios. Las restricciones enteras hacen que el problema sea combinatoriamente difícil, pero los algoritmos de descomposición explotan la estructura de escenarios para hacer tratables instancias grandes.
Historia
La programación estocástica se originó con Dantzig (1955) y Beale (1955) como LP de dos etapas. La extensión entera mixta surgió prominentemente en la década de 1990 con las adaptaciones del método en L para recurso entero por Laporte y Louveaux (1993) y el tratamiento exhaustivo en el libro de texto de Birge y Louveaux de 1997. El algoritmo C3/D2 de Sen y Higle (2005) avanzó los solucionadores escalables de SMIP, estableciendo el campo como una disciplina madura dentro de la investigación de operaciones.
Cuándo usarlo
Usar SMIP cuando las decisiones involucran opciones discretas o binarias (invertir/no invertir, número de unidades a abrir) y los parámetros de entrada clave son genuinamente inciertos con distribuciones de probabilidad cuantificables. Ideal para el diseño de redes de cadena de suministro bajo incertidumbre de demanda, expansión de capacidad energética, planificación de instalaciones de atención médica y pre-posicionamiento para respuesta a desastres. No usar cuando todas las decisiones son continuas (usar LP estocástico en su lugar), cuando la incertidumbre no puede cuantificarse significativamente como distribuciones, cuando el número de escenarios requeridos para representar la incertidumbre conduce a tamaños de modelo intratables y la descomposición no está disponible, o cuando una heurística basada en simulación es suficiente para la calidad de decisión requerida.
Limitaciones y consideraciones
- La complejidad computacional crece combinatoriamente con el número de escenarios y variables enteras; instancias grandes pueden ser intratables sin una descomposición efectiva.
- Requiere distribuciones de probabilidad explícitas o conjuntos de escenarios — modelos de incertidumbre mal especificados conducen a soluciones que rinden pobremente fuera de muestra.
- Las formulaciones de dos etapas pueden simplificar en exceso las decisiones multi-período; la SMIP multi-etapa es significativamente más difícil.
- El recurso entero en la segunda etapa destruye la convexidad explotada por los cortes estándar de Benders, requiriendo cortes en L enteros especializados.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Maneja decisiones discretas combinatorias bajo incertidumbre en un único modelo de optimización coherente.
- Produce planes de primera etapa protegidos que equilibran el rendimiento esperado en todos los escenarios.
- Las métricas VSS y EVPI proporcionan una justificación transparente del valor del modelado estocástico.
- Los algoritmos de descomposición (en L, progressive hedging) escalan a grandes conjuntos de escenarios.
- Ampliamente soportado en solucionadores comerciales (CPLEX, Gurobi) y lenguajes de modelado (AMPL, Pyomo).
Aplicaciones
- Diseño de redes de cadena de suministro con demandas de clientes inciertas y decisiones binarias de localización de instalaciones.
- Planificación de expansión de capacidad de energía eléctrica bajo generación renovable incierta y crecimiento de la demanda.
- Asignación de recursos del sistema de atención médica (personal entero, aperturas de clínicas binarias) bajo incertidumbre epidemiológica.
- Pre-posicionamiento de logística humanitaria de suministros discretos antes de escenarios de desastre.
- Optimización de portafolios financieros con costos de transacción y restricciones de lotes enteros bajo incertidumbre del mercado.
- Programación de tripulaciones de aerolíneas bajo retrasos inciertos de vuelos con variables de asignación binarias.
Cómo funciona
Cómo funciona
Identificar variables de decisión: decisiones de primera etapa x tomadas antes de que se revele la incertidumbre (enteras y/o binarias entre ellas), y variables de recurso de segunda etapa y(xi) tomadas después de que se materializa el escenario xi. Especificar coeficientes del objetivo, matrices de restricciones y la distribución de probabilidad o el conjunto discreto de escenarios para los parámetros inciertos.
Construir un conjunto finito de escenarios {xi_1, ..., xi_S} con probabilidades asociadas {p_1, ..., p_S} que aproximen la distribución subyacente. Los escenarios pueden derivarse de datos históricos, elicitación de expertos, muestreo de hipercubo latino o métodos de ajuste de momentos. La calidad del escenario afecta directamente la calidad de la solución.
Formular el equivalente determinista: minimizar c'x + sum_s p_s Q(x, xi_s) sujeto a restricciones de primera etapa e integralidad. Q(x, xi_s) es la función de valor de segunda etapa —el costo óptimo de las acciones de recurso dado x y el escenario xi_s. El programa combinado es una MIP grande cuyo tamaño crece con el número de escenarios.
Fórmula
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}Resolver utilizando algoritmos de descomposición — método en L (descomposición de Benders) para segundas etapas convexas, branch-and-cut con subproblemas de escenarios, o progressive hedging para descomposición paralela de escenarios. La integralidad en la segunda etapa requiere cortes adicionales (cortes en L enteros, lift-and-project). Los solucionadores modernos (CPLEX, Gurobi con callbacks, o bibliotecas específicas de SMIP) implementan estas rutinas.
Evaluar la solución a través del Valor de la Solución Estocástica (VSS = EEV - RP) y el Valor Esperado de la Información Perfecta (EVPI = RP - WS), donde RP es el valor óptimo del problema de recurso, EEV es el costo esperado de usar la solución determinista de valor medio, y WS es el valor de esperar y ver. Estas métricas cuantifican el beneficio de modelar explícitamente la incertidumbre.
Errores comunes
- Usar muy pocos escenarios subrepresenta la incertidumbre, produciendo soluciones demasiado confiadas; demasiados hacen que el modelo sea computacionalmente infactible.
- Confundir los roles de las variables de primera y segunda etapa conduce a formulaciones que no respetan la temporalidad de la revelación de información.
- Confiar en la solución de valor esperado (ignorando la estocasticidad) puede ser significativamente subóptimo — siempre calcular VSS para justificar el esfuerzo de SMIP.
- Negar la integralidad en la etapa de recurso cuando está realmente presente produce una relajación cuya solución puede ser infactible en la práctica.
- La configuración predeterminada del solucionador para MIP a menudo necesita ajuste (prioridades de ramificación, estrategias de corte) en los marcos de descomposición de SMIP.
Preguntas frecuentes
¿En qué se diferencia la SMIP de la Programación Entera Mixta regular?
La MIP regular optimiza bajo parámetros fijos y conocidos. La SMIP modela explícitamente parámetros inciertos como un conjunto de escenarios con probabilidades, optimizando el rendimiento esperado en todos los escenarios y asegurando que las decisiones de primera etapa se tomen antes de que se revele la incertidumbre.
¿Cuántos escenarios necesito?
No hay una regla universal. Tan solo 10-50 escenarios pueden ser suficientes para decisiones estables de primera etapa en algunos problemas; otros requieren miles. Técnicas de reducción de escenarios y pruebas de estabilidad (verificando que la solución óptima no cambie al agregar más escenarios) ayudan a determinar la adecuación.
¿Qué es el método en L?
El método en L es una descomposición de Benders adaptada para programas estocásticos. Resuelve iterativamente una MIP maestra sobre variables de primera etapa y subproblemas de escenarios, agregando cortes de optimalidad y factibilidad a la maestra hasta la convergencia. Para recurso entero, los cortes en L enteros reemplazan los cortes estándar de Benders.
¿Cuándo debería usar progressive hedging en lugar del método en L?
Progressive hedging se descompone por escenario en lugar de por estructura de subproblema, lo que lo hace adecuado para la computación paralela. Se prefiere cuando hay muchos escenarios y subproblemas grandes, y cuando el algoritmo se puede ejecutar en un clúster. El método en L generalmente se prefiere para escenarios menos numerosos y bien estructurados.
¿Puede la SMIP manejar más de dos etapas?
Sí, pero la SMIP multi-etapa requiere un árbol de escenarios que crece exponencialmente en el número de etapas, y la descomposición se vuelve sustancialmente más compleja. En la práctica, la mayoría de los modelos SMIP aplicados utilizan dos etapas, aproximando dinámicas multi-período mediante horizonte rodante o agregación.
Métodos relacionados
Fuentes
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN: 9780387982175Copiado.Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
Abrir referencia DOICopiado.