Saltar al contenido
Volver a los resultados

Programación Entera Mixta Robusta — Optimización con variables enteras bajo incertidumbre

Propuesto por
Ben-Tal & Nemirovski; Bertsimas & Sim
Año
1998–2004
Tipo
Deterministic robust reformulation of MIP under uncertainty
Familia
Simulation / optimization

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Programación Entera Mixta Robusta (RMIP, por sus siglas en inglés) combina la programación entera mixta con la optimización robusta para encontrar soluciones que permanecen factibles y casi óptimas a pesar de los parámetros inciertos.

En lugar de asumir datos fijos, protege las decisiones contra realizaciones adversas o de peor caso de las entradas inciertas, utilizando un conjunto de incertidumbre explícito para controlar el grado de conservadurismo mientras preserva la estructura combinatoria de las decisiones enteras.

La intuición detrás del método

Los programas enteros mixtos clásicos asumen que todos los datos se conocen con exactitud, pero en la práctica los costos, las demandas y los tiempos de procesamiento fluctúan. La RMIP pregunta: ¿cuáles son las mejores decisiones enteras y continuas si los parámetros inciertos toman sus peores valores plausibles dentro de un rango definido? Al incrustar la incertidumbre directamente en el modelo de optimización, la RMIP produce planes que están inmunizados contra la variación de datos sin recurrir a múltiples escenarios probabilísticos. El enfoque de presupuesto de incertidumbre de Bertsimas-Sim permite a los profesionales ajustar el equilibrio entre la robustez total y la eficiencia del caso promedio, haciendo explícita la compensación entre protección y costo.

Historia

La optimización robusta como paradigma tratable fue establecida por Ben-Tal y Nemirovski a finales de la década de 1990 para problemas continuos. Bertsimas y Sim (2004) la extendieron a programas lineales con un conjunto de presupuesto de incertidumbre que preserva la tratabilidad lineal. Trabajos posteriores integraron este marco con la programación entera, dando lugar a la RMIP, que fue ampliamente adoptada en la investigación de la cadena de suministro, la energía y el transporte a lo largo de la década de 2010.

Cuándo usarlo

Utilice RMIP cuando las decisiones implican elecciones enteras o binarias (ubicación de instalaciones, dimensionamiento de lotes, diseño de redes, programación) y algunos parámetros de entrada son inciertos pero las distribuciones de probabilidad no están disponibles o no son fiables. Es apropiado cuando las violaciones de las restricciones son inaceptables (requisitos de factibilidad estricta) y se prefiere una garantía conservadora pero determinista a la optimización del valor esperado. NO lo use cuando las distribuciones de incertidumbre están bien caracterizadas y la aproximación de la media muestral o el MIP estocástico es factible; cuando todas las variables de decisión son continuas (use LP robusta en su lugar); o cuando el conjunto de incertidumbre es tan grande que el modelo se vuelve intratable sin estrategias de descomposición.

Limitaciones y consideraciones

  • Conservadora por diseño — el objetivo en el peor caso es típicamente peor que el objetivo en el caso esperado de la programación estocástica.
  • La selección de un conjunto de incertidumbre apropiado requiere conocimiento del dominio; un conjunto mal elegido conduce a una sobreprotección o a una subprotección.
  • Las reformulaciones robustas pueden aumentar significativamente el tamaño del modelo (variables y restricciones adicionales), lo que eleva la carga computacional para instancias grandes.
  • No proporciona declaraciones de probabilidad sobre el rendimiento de la solución; el MIP estocástico es más adecuado cuando se requieren medidas de riesgo probabilísticas.

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 deterministas en el peor caso sin requerir distribuciones de probabilidad para los parámetros inciertos.
  • El parámetro de presupuesto de incertidumbre (Gamma) proporciona un control intuitivo y ajustable sobre la compensación entre robustez y optimalidad.
  • La reformulación preserva la estructura MIP, lo que permite el uso de solucionadores comerciales maduros y tecnología de ramificación y corte.
  • Aplicable a problemas combinatorios difíciles como el diseño de redes, la ubicación de instalaciones y la programación de la producción.
  • Computacionalmente más tratable que el MIP estocástico completo con muchos escenarios.

Aplicaciones

  • Diseño de redes de cadena de suministro bajo demanda y tiempos de entrega inciertos
  • Planificación de la expansión de la capacidad del sistema energético con generación renovable incierta
  • Ubicación de instalaciones sanitarias bajo incertidumbre de la demanda de pacientes
  • Programación de tripulaciones aéreas con retrasos de vuelos inciertos
  • Dimensionamiento de lotes de fabricación bajo costos y tiempos de procesamiento inciertos
  • Enrutamiento de redes de telecomunicaciones con volúmenes de tráfico inciertos

Cómo funciona

Cómo funciona

1

Formule el MIP nominal: identifique las variables de decisión (binarias o enteras y, continuas x), la función objetivo y las restricciones. Determine qué parámetros (coeficientes de costo, valores del lado derecho, entradas de la matriz tecnológica) son inciertos y deben protegerse.

2

Defina un conjunto de incertidumbre U para los parámetros inciertos. Las opciones comunes son conjuntos de caja (rangos de intervalo para cada parámetro), conjuntos elipsoidales (incertidumbre correlacionada) o el conjunto de presupuesto de Bertsimas-Sim (como máximo Gamma parámetros se desvían simultáneamente), donde Gamma controla el conservadurismo.

3

Reemplace cada restricción incierta con su contraparte robusta, que debe cumplirse para todas las realizaciones en U. Para la incertidumbre de presupuesto, esto produce una reformulación tratable: la restricción original se aumenta con un término de penalización que controla la suma de desviaciones en el peor caso. El resultado es un modelo más grande pero aún tratable como MIP.

4

Resuelva el MIP robusto reformulado con un solucionador estándar de ramificación y acotamiento (branch-and-bound) o ramificación y corte (branch-and-cut) (por ejemplo, CPLEX, Gurobi, SCIP). La reformulación preserva los requisitos de integralidad en y. Para instancias a gran escala, la descomposición de Benders o los métodos de planos de corte pueden descomponer el problema.

5

Evalúe la solución robusta mediante: (a) el cálculo de su valor objetivo bajo parámetros nominales y de peor caso, (b) la comparación con la solución de programación estocástica utilizando escenarios de Monte Carlo, y (c) la presentación del precio de la robustez — el costo adicional pagado por la protección contra la incertidumbre.

Errores comunes

  • Elegir Gamma=0 (sin presupuesto de incertidumbre) reproduce el MIP nominal y no ofrece protección; un Gamma demasiado grande conduce a soluciones excesivamente conservadoras e inviables operativamente.
  • Tratar todos los parámetros como inciertos simultáneamente puede hacer que la reformulación sea intratable — identifique los parámetros inciertos críticos para proteger selectivamente.
  • Ignorar la estructura de correlación de las incertidumbres puede resultar en un conjunto de incertidumbre excesivamente pesimista; los conjuntos elipsoidales son preferibles cuando se conocen las correlaciones.
  • Informar solo el objetivo del peor caso sin compararlo con los puntos de referencia nominales o estocásticos da una imagen incompleta de la calidad de la solución.

Preguntas frecuentes

¿En qué se diferencia la RMIP de la programación entera mixta estocástica?

El MIP estocástico utiliza distribuciones de probabilidad y optimiza el rendimiento esperado en escenarios muestreados, mientras que la RMIP protege contra el peor caso dentro de un conjunto de incertidumbre sin requerir información distribucional. La RMIP proporciona una única solución robusta determinista; el MIP estocástico proporciona una política que es buena en promedio.

¿Qué es el 'precio de la robustez' y qué tan grande es típicamente?

El precio de la robustez es el aumento porcentual en el valor objetivo en comparación con el óptimo nominal (sin incertidumbre). Bertsimas y Sim demuestran que crece aproximadamente linealmente con Gamma, pero se mantiene modesto para valores de presupuesto típicos, a menudo del 5 al 15% en aplicaciones prácticas.

¿Puede la RMIP manejar valores inciertos del lado derecho, así como coeficientes de costo inciertos?

Sí. La incertidumbre en los lados derechos de las restricciones conduce a restricciones de factibilidad robusta, mientras que la incertidumbre en los coeficientes objetivos afecta la optimalidad robusta. Ambos pueden manejarse simultáneamente dentro del marco del presupuesto de incertidumbre, aunque la estructura de reformulación difiere.

¿Es la RMIP resoluble con solucionadores MIP estándar?

Para el conjunto de presupuesto de Bertsimas-Sim, la reformulación robusta sigue siendo un MIP y puede resolverse directamente con solucionadores como CPLEX o Gurobi. Los conjuntos de incertidumbre elipsoidales producen programas de cono de segundo orden enteros mixtos (MISOCP, por sus siglas en inglés), que también son compatibles con los solucionadores modernos.

¿Cuándo debo preferir un conjunto de incertidumbre de caja sobre el conjunto de presupuesto de incertidumbre?

Un conjunto de caja protege contra todos los parámetros que se desvían simultáneamente a sus extremos, lo que a menudo es excesivamente conservador. El conjunto de presupuesto (Gamma) se prefiere cuando las desviaciones simultáneas en el peor caso de todos los parámetros son poco probables, ya que produce soluciones menos conservadoras y más rentables.

Métodos relacionados

Fuentes

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    Abrir referencia DOI
    Copiado.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Copiado.