Learning to Cut: Reinforcement Learning for Benders Decomposition

Resumen Técnico: Aprender a Cortar: Aprendizaje por Refuerzo para la Descomposición de Benders

Enunciado del Problema
La Descomposición de Benders (BD) es un enfoque estándar para resolver programas estocásticos de dos etapas, que modelan la toma de decisiones bajo incertidumbre separando las decisiones de "aquí y ahora" de la primera etapa de las acciones de recurso de "esperar y ver" de la segunda etapa. Aunque es efectiva, la BD clásica a menudo sufre de una convergencia lenta. Esta ineficiencia surge de una compensación en la gestión de cortes: añadir todos los cortes por escenario (formulación multicorte) crea una aproximación más ajustada de la función de recurso, pero agranda significativamente el problema maestro, ralentizando las resoluciones posteriores; por el contrario, agregar los cortes en un solo corte (formulación monocorte) mantiene el problema maestro pequeño pero produce aproximaciones más débiles. Los enfoques heurísticos existentes, como seleccionar solo los cortes más violados o utilizar cortes óptimos de Pareto, intentan gestionar esto, pero a menudo dependen de reglas deterministas que pueden no adaptarse bien a estructuras de problemas variables o entradas de datos.

Metodología
Los autores proponen Aprendizaje por Refuerzo para BD (RLBD), un marco que modela la selección de cortes como un problema de toma de decisiones secuencial dentro de un Proceso de Decisión de Markov (MDP) de horizonte finito con descuento.

• Formulación MDP:

  • Espacio de Estados ($S$): El estado en cada iteración $t$ captura tanto estadísticas globales de convergencia (índice de iteración, límites inferior/superior, brecha de optimalidad, tasas de reducción de la brecha y tiempos de resolución del problema maestro/subproblema) como características locales de los cortes. Las características locales para cada corte candidato incluyen niveles de violación, normas de variables duales, coeficientes de corte y la frecuencia histórica de cortes generados por el mismo escenario.
  • Espacio de Acciones ($A$): La acción consiste en seleccionar un subconjunto de $K$ cortes candidatos de los cortes por escenario disponibles para añadirlos al problema maestro.
  • Función de Recompensa ($r$): La recompensa es una suma ponderada de tres componentes: (1) un término basado en la brecha que refleja la reducción logarítmica de la brecha de optimalidad (fomentando la convergencia), (2) un término negativo proporcional al tiempo de resolución del problema maestro (fomentando la eficiencia) y (3) una penalización por paso (fomentando trayectorias más cortas).
  • Dinámicas de Transición: El entorno transita al siguiente estado resolviendo el problema maestro actualizado con los cortes seleccionados, generando nuevos subproblemas y calculando nuevos límites y estadísticas.

• Parametrización de la Política y Entrenamiento:

  • La política de selección de cortes $\pi_\theta$ está parametrizada por una red neuronal feedforward compartida. La red procesa un vector concatenado de información de estado global y características locales de cortes para cada corte candidato, generando un logit escalar. Una función softmax convierte estos logits en una distribución de probabilidad.
  • La política se entrena utilizando el algoritmo REINFORCE (un método de gradiente de política). Durante los episodios de entrenamiento, el agente muestrea una secuencia de $K$ cortes sin reemplazo basándose en la distribución de la política actual. Los parámetros de la política se actualizan mediante ascenso de gradiente para maximizar la recompensa descontada acumulada esperada.
  • Inferencia: Durante las pruebas, la política entrenada se aplica de manera codiciosa, seleccionando los $K$ cortes superiores con los logits más altos para cada nueva instancia del problema.

Contribuciones Clave

1. Política de Selección de Cortes Estocástica: A diferencia de las heurísticas deterministas, RLBD emplea una política estocástica que asigna probabilidades de selección basadas tanto en el progreso algorítmico global como en las características locales de los cortes. Esto permite al agente explotar cortes informativos mientras mantiene la capacidad de explorar candidatos alternativos que pueden volverse críticos más adelante.
2. Capacidad de Generalización: El marco está diseñado para generalizar a problemas con estructuras similares pero entradas de datos variables (por ejemplo, diferentes realizaciones de demanda) y dimensiones de variables de decisión (por ejemplo, diferentes números de instalaciones o clientes), sin necesidad de reentrenamiento.
3. Mejoras de Rendimiento: El enfoque demuestra mejoras sustanciales sobre los puntos de referencia existentes, incluida la BD convencional y LearnBD (un enfoque de aprendizaje supervisado que utiliza Máquinas de Vectores de Soporte).

Resultados Experimentales
Los autores evaluaron RLBD en un problema de ubicación de estaciones de carga para vehículos eléctricos (VE) estocástico de dos etapas. Los experimentos implicaron el entrenamiento en una instancia específica y la prueba en instancias con tamaños de problema variables ($8\times12$, $10\times15$, $20\times30$) y distribuciones de demanda (Normal, sesgada a la izquierda y sesgada a la derecha).

• Instancias Pequeñas a Medianas: Para instancias con configuraciones de $8\times12$ y $10\times15$, RLBD logró una reducción del tiempo computacional de aproximadamente cinco veces en comparación con la BD convencional y LearnBD, manteniendo brechas de optimalidad comparables. Esta ganancia de eficiencia se atribuyó principalmente a la selección adaptativa de cortes, lo que resultó en tiempos de resolución del problema maestro significativamente menores.
• Instancias Grandes: Para instancias más grandes ($20\times30$) donde todos los métodos fallaron en converger dentro del límite de tiempo de una hora, RLBD logró una brecha de optimalidad final menor (aprox. 28–29%) en comparación con los puntos de referencia (aprox. 35–39%).
• Sensibilidad a Hiperparámetros: El estudio identificó que un peso de recompensa de $\alpha=0.01$ (reducción de brecha) y $\lambda=0.001$ (penalización por paso), combinado con la adición de $K=10$ cortes por iteración, produjo la convergencia y eficiencia más estables.
• Perspectivas Gerenciales: El análisis de la política aprendida reveló que tiende a priorizar cortes de escenarios con mayor demanda total, exposición a penalizaciones y exposición a ingresos, lo que sugiere que el modelo identifica con éxito realizaciones de alta carga como críticas para ajustar la formulación.

Significado y Afirmaciones
El artículo afirma que RLBD ofrece una alternativa robusta y adaptable a las estrategias tradicionales de gestión de cortes. Al enmarcar la selección de cortes como un problema de aprendizaje, el método supera la rigidez de las heurísticas deterministas. Los autores enfatizan que la política entrenada exhibe una fuerte generalización, manejando efectivamente cambios en la distribución y variaciones en las dimensiones del problema sin requerir reentrenamiento. Los resultados sugieren que integrar el aprendizaje por refuerzo en el bucle de BD puede mejorar significativamente la eficiencia computacional para programas estocásticos de dos etapas, particularmente en escenarios donde el tamaño del problema maestro se convierte en un cuello de botella. El trabajo posiciona a RLBD como un método viable para mejorar la escalabilidad de la optimización estocástica en aplicaciones del mundo real como la ubicación de instalaciones y la gestión de la cadena de suministro.