Programación Lineal Robusta — Optimización Bajo Incertidumbre
- Propuesto por
- Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
- Año
- 1999–2004
- Tipo
- Uncertainty-robust linear optimization
- 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 Lineal Robusta (RLP) extiende la programación lineal clásica para manejar la incertidumbre en los datos del problema — coeficientes de costo, coeficientes de restricciones o términos independientes — exigiendo que las soluciones permanezcan factibles y casi óptimas en todas las realizaciones de parámetros inciertos dentro de un conjunto de incertidumbre definido.
Reemplaza las suposiciones probabilísticas con garantías de peor caso, haciéndola práctica cuando el conocimiento distributivo es limitado.
La intuición detrás del método
La programación lineal ordinaria encuentra la mejor solución asumiendo que todos los datos se conocen exactamente. En la práctica, los coeficientes se estiman, pronostican o miden con error. La RLP pregunta: ¿cuál es la mejor decisión que permanece factible sin importar cómo varíen los parámetros inciertos dentro de un rango plausible? El analista especifica un conjunto de incertidumbre — una caja, elipsoide o región politópica — y el solucionador encuentra el plan que es óptimo para el peor caso dentro de ese conjunto. La formulación de presupuesto de incertidumbre de Bertsimas y Sim permite al analista ajustar el conservadurismo: un parámetro Gamma controla cuántos coeficientes pueden desviarse simultáneamente, interpolando entre el LP nominal y el peor caso totalmente conservador.
Historia
La optimización robusta fue establecida sobre una base teórica firme por Ben-Tal y Nemirovski (1999), quienes demostraron que los programas lineales inciertos con conjuntos de incertidumbre elipsoidales producen programas de cono de segundo orden tratables. Bertsimas y Sim (2004) introdujeron el marco de presupuesto de incertidumbre, que mantiene la reformulación como un programa lineal y hace que la robustez sea ajustable a través de un solo parámetro, expandiendo enormemente la adopción práctica en investigación de operaciones e ingeniería.
Cuándo usarlo
Utilizar RLP cuando la incertidumbre de los datos es real pero las distribuciones de probabilidad son desconocidas o poco fiables, como en la planificación de la cadena de suministro con demanda incierta, el despacho de energía con errores de pronóstico o la construcción de carteras financieras bajo rendimientos ambiguos. Es apropiado cuando la factibilidad de las restricciones bajo todos los escenarios es innegociable. Evitar RLP cuando la incertidumbre es insignificante en relación con la escala del objetivo, cuando las distribuciones de probabilidad están bien caracterizadas (la programación estocástica puede ser preferible), cuando el número de parámetros inciertos es tan grande que la contraparte robusta se vuelve intratable, o cuando el escenario de peor caso es irrealistamente pesimista para la aplicación.
Limitaciones y consideraciones
- La orientación al peor caso puede producir soluciones excesivamente conservadoras cuando los escenarios extremos son muy poco probables.
- Los conjuntos de incertidumbre elipsoidales producen programas de cono de segundo orden tratables pero ya no LPs puros, lo que aumenta los requisitos del solucionador.
- Requiere que el analista especifique un conjunto de incertidumbre, que es en sí mismo una elección de modelado que afecta significativamente los resultados.
- No proporciona directamente declaraciones de probabilidad de violación; la programación estocástica es mejor si las probabilidades de cola importan.
- Se degenera al LP nominal cuando Gamma = 0, sin ofrecer protección contra la incertidumbre.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Proporciona garantías de factibilidad de peor caso duras sin requerir suposiciones distributivas.
- La formulación de presupuesto de Bertsimas-Sim produce una contraparte de LP tratable resoluble con solucionadores comerciales.
- El presupuesto de robustez Gamma le da al analista un control intuitivo para equilibrar la calidad de la solución con el conservadurismo.
- Computacionalmente eficiente — las contrapartes robustas para conjuntos de presupuesto tienen una complejidad similar a la del LP original.
- Particularmente bien adaptado a problemas donde la violación de restricciones es costosa o insegura.
Aplicaciones
- Diseño de redes de cadenas de suministro con costos de transporte e incertidumbre en la demanda
- Despacho de sistemas de energía eléctrica bajo incertidumbre en pronósticos de energía renovable
- Optimización de carteras con rangos ambiguos de rendimiento de activos
- Planificación de tratamiento de radioterapia con incertidumbre en el movimiento del paciente
- Programación de tripulaciones de aerolíneas bajo incertidumbre en retrasos de vuelos
- Asignación de recursos hídricos con incertidumbre en precipitación y evaporación
Cómo funciona
Cómo funciona
Formular el programa lineal nominal: minimizar una función objetivo lineal c^T x sujeta a restricciones de desigualdad lineal Ax <= b y no negatividad. Identificar qué coeficientes — típicamente entradas de la matriz de restricciones a_ij — son inciertos. Este paso imita la modelización estándar de LP pero marca cada parámetro incierto.
Fórmula
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0Construir un conjunto de incertidumbre U que capture el rango de valores plausibles de los parámetros sin requerir una distribución de probabilidad. Las opciones comunes son conjuntos de caja (cada parámetro varía independientemente dentro de [a_bar - a_hat, a_bar + a_hat]), conjuntos elipsoidales (Ben-Tal y Nemirovski, 1999) y conjuntos de presupuesto (Bertsimas y Sim, 2004). El parámetro de presupuesto Gamma limita cuántos parámetros pueden tomar simultáneamente sus valores de peor caso.
Fórmula
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}Reemplazar cada restricción incierta con su contraparte robusta: exigir factibilidad para cada realización en U. Esto transforma el problema original en un programa semi-infinito — infinitas restricciones, una por cada elemento de U.
Fórmula
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall iDerivar un equivalente determinista tratable. Para conjuntos de incertidumbre de presupuesto, la contraparte robusta se reformula como un LP estándar o un LP mixto-entero de tamaño similar, resoluble con solucionadores convencionales. La reformulación clave introduce variables auxiliares que linealizan la maximización interna sobre el conjunto de incertidumbre.
Fórmula
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_iResolver el LP reformulado utilizando un solucionador estándar (simplex o punto interior). Evaluar la solución: verificar la violación de restricciones en el peor caso en todo el conjunto de incertidumbre, reportar el precio de la robustez (el aumento del objetivo en relación con el LP nominal) y realizar un análisis de sensibilidad sobre el presupuesto de robustez Gamma.
Errores comunes
- Establecer Gamma demasiado alto hace que todas las restricciones sean de peor caso simultáneamente, produciendo una solución excesivamente conservadora y costosa.
- Especificar incorrectamente el conjunto de incertidumbre (por ejemplo, ignorar la estructura de correlación) puede llevar a una protección excesiva o insuficiente.
- Confundir LP robusto con LP estocástico: el RLP maximiza el rendimiento en el peor caso, no el rendimiento esperado.
- Ignorar el informe del precio de la robustez — siempre comparar el objetivo robusto con el objetivo del LP nominal para cuantificar el costo del conservadurismo.
- Aplicar RLP a problemas con variables enteras sin cambiar a la formulación mixta-entera robusta, que requiere diferentes reformulaciones.
Preguntas frecuentes
¿Cómo difiere el LP Robusto del LP Estocástico?
El LP Estocástico optimiza el rendimiento esperado dada una distribución de probabilidad sobre escenarios, requiriendo conocimiento distributivo. El LP Robusto optimiza el rendimiento en el peor caso sobre un conjunto de incertidumbre, requiriendo solo límites — sin distribución de probabilidad. El LP Robusto se prefiere cuando las distribuciones son poco fiables; el LP Estocástico se prefiere cuando están bien estimadas.
¿Cuál es el precio de la robustez?
El precio de la robustez es el aumento en el valor del objetivo (costo) de la solución robusta en relación con la solución del LP nominal. Bertsimas y Sim (2004) demostraron que este precio crece solo como la raíz cuadrada del número de parámetros inciertos para conjuntos de presupuesto, haciendo que la robustez sea sorprendentemente asequible.
¿Qué es el presupuesto de robustez Gamma?
Gamma es un parámetro en el modelo de Bertsimas-Sim que controla cuántos coeficientes inciertos pueden tomar simultáneamente sus valores de peor caso. Gamma = 0 recupera el LP nominal; Gamma = n protege contra la desviación de los n parámetros a la vez. Los analistas suelen elegir Gamma basándose en los límites aceptables de probabilidad de violación.
¿Requiere el LP Robusto un solucionador especial?
No. Para conjuntos de incertidumbre de caja y presupuesto, la contraparte robusta es en sí misma un programa lineal, resoluble con cualquier solucionador de LP estándar (CPLEX, Gurobi, HiGHS, etc.). Los conjuntos elipsoidales requieren un solucionador de programas de cono de segundo orden, que también está ampliamente soportado.
¿Cuándo debería usar Programación Mixta-Entera Robusta en su lugar?
Si las variables de decisión deben ser enteras (por ejemplo, decisiones binarias de sí/no, tamaños de lote), la contraparte robusta contiene variables enteras y se convierte en un Programa Mixto-Entero Robusto. El enfoque del conjunto de incertidumbre es el mismo, pero la reformulación y los requisitos del solucionador cambian en consecuencia.
Métodos relacionados
Fuentes
Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
Abrir referencia DOICopiado.Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.
Abrir referencia DOICopiado.