A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

Resumen Técnico: Un Método Computacional para Resolver el Problema de Reabastecimiento Conjunto Estocástico en Altas Dimensiones

Formulación del Problema
El artículo aborda el Problema de Reabastecimiento Conjunto Estocástico (SJRP), un desafío clásico de gestión de inventarios que implica la coordinación de sistemas de inventario de múltiples artículos, donde se incurre en un costo fijo de reabastecimiento de manera conjunta para los artículos pedidos simultáneamente. En la formulación de tiempo discreto considerada, un gerente de almacén revisa periódicamente los niveles de inventario y decide si realizar pedidos para subconjuntos de $d$ artículos. El sistema enfrenta demandas aleatorias, costos de mantenimiento lineales y penalizaciones por retrasos. El objetivo es minimizar el costo total esperado descontado sobre un horizonte infinito.

La dificultad central radica en la "maldición de la dimensionalidad". Bajo costos fijos de reabastecimiento no nulos, las decisiones a nivel de artículo se vuelven interdependientes, lo que provoca que los espacios de estado y decisión del Proceso de Decisión de Markov (MDP) asociado crezcan exponencialmente con el número de artículos ($d$). En consecuencia, las técnicas estándar de programación dinámica se vuelven computacionalmente intratables para configuraciones de alta dimensionalidad (por ejemplo, $d \ge 50$), y la literatura existente ha dependido en gran medida de políticas heurísticas con garantías teóricas limitadas sobre optimalidad.

Metodología
Para superar estas barreras computacionales, los autores proponen un método computacional novedoso basado en simulación que conecta el control de inventario en tiempo discreto con la teoría de control impulsivo en tiempo continuo y el aprendizaje profundo.

1. Aproximación en Tiempo Continuo: El SJRP en tiempo discreto se aproxima mediante un problema de control impulsivo en tiempo continuo. En esta formulación, el proceso de demanda acumulada se modela como un proceso gaussiano (movimiento browniano con deriva), y el gerente puede intervenir en cualquier momento para saltar instantáneamente el estado del inventario a un nivel superior a un costo fijo. Esta aproximación permite una representación probabilística de la función de valor que es más susceptible a técnicas de solución de alta dimensionalidad.

2. Representación Probabilística mediante EDP Estocásticas Atrás (BSDE) Constrainadas: A diferencia de los métodos estándar de BSDE profundas que se basan en igualdades casi seguras, la función de valor de este problema de control impulsivo se caracteriza como la solución mínima de una BSDE restringida. Esto conduce a una identidad estocástica que involucra una desigualdad casi segura en lugar de una igualdad. Específicamente, la función de valor $V(x)$ es el supremo de los valores $v$ que satisfacen una condición objetivo estocástica que involucra el proceso de referencia, los costos de funcionamiento y los costos de salto.

3. Solucionador de Redes Neuronales Profundas: Los autores desarrollan un algoritmo computacional para resolver esta BSDE restringida utilizando redes neuronales profundas.

   • Función de Pérdida: Se construye una función de pérdida novedosa para manejar la restricción de desigualdad. Incluye un término de penalización por violaciones de la desigualdad estocástica, ponderado por un parámetro de penalización ajustable $\beta$.
   • Proceso de Referencia: Se utiliza una política de referencia cuidadosamente diseñada (una política aleatorizada de orden hasta un nivel máximo impulsada por un proceso de Poisson) para generar trayectorias de muestra. Este proceso está diseñado para equilibrar la exploración y la explotación, asegurando que las redes neuronales se entrenen en regiones relevantes del espacio de estados.
   • Estrategia de Entrenamiento: Para garantizar la estabilidad, los autores emplean un cronograma conjunto para el parámetro de penalización $\beta$ y la tasa de aprendizaje. La penalización se incrementa gradualmente mientras la tasa de aprendizaje disminuye, permitiendo que la red aprenda primero la estructura general y luego haga cumplir estrictamente las restricciones de desigualdad.

4. Extracción de la Política: Una vez que la función de valor $V$ y su gradiente $\nabla V$ son aproximados por redes neuronales, se deriva una política implementable. La política verifica una condición de "no acción" derivada de la ecuación de Hamilton-Jacobi-Bellman (HJB). Si se viola la condición, se realiza un pedido. El vector de orden hasta un nivel máximo se determina minimizando la suma de la función de valor aproximada y el costo de pedido, un paso que puede precomputarse de manera eficiente.

Contribuciones Clave

• Escalabilidad en Alta Dimensionalidad: El método resuelve con éxito el SJRP para dimensiones de hasta al menos 50 (50 referencias de stock), un régimen donde las soluciones óptimas basadas en MDP tradicionales son intratables.
• Diseño Novel de Pérdida: El artículo introduce una función de pérdida específica y un cronograma de entrenamiento adaptados al marco de BSDE restringida requerido para el control impulsivo, abordando el desafío de las desigualdades casi seguras que los métodos estándar de BSDE profunda no manejan.
• Ingeniería del Proceso de Referencia: El diseño del proceso de referencia con saltos dependientes del estado se destaca como una innovación crítica para garantizar un entrenamiento eficiente y la cobertura del espacio de estados relevante.
• Implementación: Los autores proporcionan una tubería completa desde la aproximación del problema hasta la extracción de la política, incluyendo estrategias detalladas de ajuste de hiperparámetros y resultados computacionales.

Resultados
La política de Red Neuronal (NN) propuesta se evaluó en 43 problemas de prueba a través de las dimensiones 2, 12 y 50, con variabilidad de demanda (baja, media, alta) y estructuras de costos variables.

• Dimensiones Bajas ($d=2$): La política NN se comparó contra la política óptima verdadera derivada mediante técnicas estándar de solución de MDP. Los resultados muestran que la política NN se desempeña dentro del 1% del costo óptimo y rastrea de cerca la geometría de los límites de decisión óptimos.
• Dimensiones Altas ($d=12$ y $d=50$): Dado que las soluciones óptimas son intratables, la política NN se comparó con heurísticas de última generación: revisión periódica $(R, S)$, $(Q, S)$, híbrida $(R, Q, S)$, can-order e independientes $(s, S)$.
  • En 12 dimensiones, la política NN igualó o superó a la mejor referencia en todos los casos. En escenarios de variabilidad media y alta, a menudo superó a la mejor heurística por márgenes significativos (por ejemplo, hasta un 28% de mejora sobre $(R, S)$ en casos específicos de alta variabilidad).
  • En 50 dimensiones, la política NN superó consistentemente a la mejor heurística disponible en todos los casos de prueba, con brechas de rendimiento que alcanzaron hasta el 5.59%.
• Eficiencia Computacional: El tiempo de entrenamiento escala moderadamente con la dimensión (por ejemplo, ~4 horas para 50 dimensiones en una sola GPU), evitando el crecimiento exponencial típico de los métodos basados en cuadrículas.

Significado y Afirmaciones
El artículo afirma que su método proporciona un enfoque computacionalmente viable para obtener políticas casi óptimas para problemas de reabastecimiento conjunto estocástico de alta dimensionalidad, un desafío de larga data en la gestión de operaciones. Al aprovechar el aprendizaje profundo para resolver el problema subyacente de control impulsivo de alta dimensionalidad, los autores demuestran que es posible igualar o superar el rendimiento de las mejores heurísticas existentes sin depender de suposiciones estructurales restrictivas. Los autores señalan que, aunque el método se aplica actualmente al SJRP con costos lineales y vectores de pedido sin restricciones, el marco es generalizable a otros problemas de control impulsivo, incluidos aquellos en ingeniería financiera (por ejemplo, gestión de flujos de efectivo) y cadenas de suministro con tiempos de entrega o ventas perdidas, aunque estas extensiones se dejan para trabajos futuros. El artículo enfatiza que la política propuesta no es meramente una heurística, sino una aproximación basada en datos del control óptimo derivada de una formulación probabilística rigurosa.