Descenso Discreto Estocástico

La optimización estocástica abarca una clase de problemas de optimización matemática en los cuales la función objetivo varía debido a la incertidumbre. Dada la incertidumbre irreducible del futuro, casi todos los problemas de toma de decisiones en supply chain califican como problemas de optimización estocástica. Un optimizador estocástico es un componente esencial de la optimización de supply chain: utiliza probabilistic forecasts como insumos y devuelve decisiones optimizadas ajustadas al riesgo.

Lokad ha sido pionero en un enfoque específico para esta optimización, conocido como el descenso discreto estocástico. Este paradigma de programación aborda específicamente la complejidad de los problemas de supply chain que involucran incertidumbre, basándose en el concepto más amplio de optimización estocástica para ofrecer decisiones robustas a gran escala.

Optimización estocástica en Movimiento

Probabilistic Forecasts and Sequential Decision-Making

Decision-Making under Uncertainty in Supply Chain

Stochastic Optimization of Supply Chain Decisions

The Future shaping the Past in Supply Chain

Descripción general de la tecnología

Desde 2016, Lokad ha optimizado supply chain mayormente a través de probabilistic forecasts. Sin probabilistic forecasts, las decisiones optimizadas se vuelven inevitablemente frágiles, siendo susceptibles incluso a leves variaciones en la demanda o en el lead time. En contraste, las decisiones optimizadas con probabilistic forecasts son robust. Aunque se pueden calcular decisiones robustas utilizando heurísticas “greedy” simples relativamente sencillas, dichas heurísticas a menudo no logran manejar restricciones más complejas.

En 2021, Lokad introdujo su primera tecnología de optimización estocástica de propósito general, a la que llamamos descenso discreto estocástico. Esta innovación aborda las deficiencias de las heurísticas greedy cuando se enfrentan a situaciones de supply chain no lineales. Conceptualmente, los Supply Chain Scientists de Lokad diseñan una cadena de procesamiento de datos con los siguientes pasos:

1. Preparar los datos históricos.
2. Generar probabilistic forecasts.
3. Producir decisiones robustas.

Los datos históricos se preparan utilizando las capacidades generales de ingeniería de datos de Envision, siendo Envision el lenguaje específico de dominio de Lokad. Luego, se generan probabilistic forecasts mediante programación diferenciable, un paradigma ideal para el modelado probabilístico—reconocido como ciudadano de primera clase en Envision. Finalmente, las decisiones robustas se derivan utilizando el descenso discreto estocástico, ofrecido como un paradigma de programación dentro de Envision.

En última instancia, los pasos (1), (2) y (3) se ejecutan todos dentro de Envision.

Solvers tradicionales y sus límites

La optimización matemática es un área bien establecida dentro de la informática. La mayoría de los productos de software dedicados a la optimización matemática se empaquetan como solvers. Cada solver normalmente ofrece su propio lenguaje específico de dominio (DSL), permitiendo a los usuarios optimizar matemáticamente una clase específica de problemas. Aunque existen muchos solvers en el mercado, incluyendo varias opciones de código abierto, ninguno aborda adecuadamente las realidades de los problemas de supply chain.

1. Muy pocos solvers manejan el caso estocástico. Casi todas las soluciones existentes se centran en el escenario determinístico, donde la incertidumbre está ausente. Desafortunadamente, no se puede simplemente “reutilizar” un solver determinístico para casos estocásticos sin introducir un nivel inaceptable de aproximación.

2. La mayoría de los solvers no son lo suficientemente escalables. Los problemas de supply chain pueden crecer de manera extremadamente grande: un millón de SKUs puede traducirse en decenas de millones de variables una vez modelados para optimización. Particionar el supply chain solo para acomodar al solver no es viable. El solver debe manejar de forma nativa decenas de millones de variables.

3. Muchos solvers carecen de la expresividad adecuada. La función objetivo a menudo no se puede asumir que sea lineal, cuadrática o incluso convexa. Es inaceptable distorsionar el problema bajo suposiciones matemáticas simplistas simplemente para adaptarse a las limitaciones del solver. En consecuencia, los solvers deben ofrecer paradigmas de programación altamente expresivos.

Después de revisar el panorama existente de herramientas de optimización matemática, concluimos que desarrollar nuestra propia tecnología era la única solución viable.

Bajo el capó

Lokad adopta un enfoque algo poco ortodoxo hacia la optimización estocástica. En lugar de empaquetar la tecnología como un solver convencional, abordamos el problema a través de un paradigma de programación dedicado conocido como descenso discreto estocástico. Este enfoque es crucial para aprovechar las ideas y la experiencia de nuestros Supply Chain Scientists.

Este paradigma de programación utiliza el stochastic gradient descent (SGD) porque escala de manera extremadamente eficiente—por órdenes de magnitud más allá de los métodos tradicionales de optimización no convexa. Sin embargo, SGD no es naturalmente adecuado para problemas discretos (y prácticamente todos los problemas de supply chain son discretos). Dado que las cantidades de reposición, producción o transferencia son enteros, los resultados fraccionarios no tienen sentido.

Para superar esta limitación, el descenso discreto estocástico introduce una representación diferenciable alternativa del problema original. Esta representación cuenta con un conjunto más amplio de dimensiones continuas y de valores reales, y sirve efectivamente como una parametrización de la solución discreta. A diferencia del modelo discreto original—donde los gradientes se degeneran a cero debido a efectos de enteros—esta alternativa produce gradientes no degenerados adecuados para SGD.

La principal limitación del descenso discreto estocástico es su incapacidad para abordar problemas combinatorios verdaderamente complejos, donde las soluciones están tan fuertemente restringidas que no se pueden iterar mediante ningún tipo de descenso directo. Dichos problemas requieren latent optimization, una técnica de optimización posterior también desarrollada por Lokad.

Ejemplos

Optimizar decisiones frente a un futuro incierto es un desafío. Muchos escenarios de supply chain exigen optimización estocástica para una resolución adecuada.

Reabastecimientos en tiendas de moda

Considera una red minorista que reabastece tiendas con objetivos específicos de surtido. Por ejemplo, asegurar que todas las tallas estén disponibles para una prenda es a menudo más crítico que ofrecer cada color, especialmente si algunos colores son muy similares. Si un cliente no encuentra la talla adecuada, se va. Por el contrario, abastecer únicamente de colores “populares” o neutrales hace que la tienda sea menos atractiva visualmente, reduciendo su atractivo general. Por ello, se deben incluir artículos “de colores vivos”, aunque su volumen de ventas pueda ser menor, y su presencia total en la tienda debe mantenerse cuidadosamente equilibrada.

Sin la perspectiva de surtido, la distribución a tiendas se puede manejar con una optimización greedy simple, seleccionando cada unidad adicional en base a retornos económicos decrecientes. Este enfoque greedy funciona cuando los artículos se tratan como independientes. Sin embargo, una vez que se introducen los objetivos de surtido, surgen interdependencias, y añadir una unidad extra afecta la deseabilidad de otros productos—debido a las relaciones de talla y color, como se describió anteriormente.

Mediante el descenso discreto estocástico, Lokad entrega planes de distribución robustos que optimizan el clásico compromiso entre el sobrestock y los costos por faltante de stock, al mismo tiempo que abordan factores económicos adicionales—como garantizar la presencia (o ausencia) de colores o tallas específicas—para mejorar el atractivo general de la tienda. Además, dado que esta optimización se realiza a nivel de red, cada unidad asignada a una tienda en particular se evalúa en función de las necesidades de todas las demás tiendas.

Reparaciones de motores de aeronaves

Ahora considera el desafío de reparar motores de aeronaves. Cuando llega un motor, no está claro qué piezas serán necesarias porque su lista de materiales varía en función de su condición específica—una lista de materiales verdaderamente estocástica. Además, debido al diseño del motor (esencialmente una serie de capas concéntricas), las primeras piezas identificadas como necesarias durante el desmontaje terminan siendo requeridas al final durante el montaje. Dado que todo el ciclo de reparación puede exceder los dos meses, mantener esas primeras piezas en stock podría no ser inmediatamente crítico; solo se vuelven esenciales al final del proceso. Por el contrario, las piezas ubicadas en las capas más internas del motor se necesitan de inmediato, ya que el montaje no puede continuar sin ellas.

Una optimización estocástica—específicamente, el descenso discreto estocástico—permite una priorización robusta de las inversiones en piezas, ayudando al proveedor de MRO (Maintenance, Repair, and Overhaul) a minimizar los tiempos de reparación de motores de aeronaves. Para cada artículo a comprar, la cuestión central se convierte en: “Dado este presupuesto, ¿cuántos días de retraso en la reparación puedo evitar?” De esta manera, las compras de piezas se priorizan estratégicamente para reducir el tiempo de inactividad—lo cual es crucial ya que al MRO se le paga por entregar motores operativos, y cualquier retraso representa una pérdida directa tanto para el MRO como para la aerolínea. Un enfoque greedy simple falla aquí porque las dependencias entre piezas pueden desencadenar retrasos en cascada. Por el contrario, si el MRO decide no mantener en stock ciertas piezas, puede que no afecte el cronograma general si esas piezas pueden obtenerse en paralelo mientras se esperan componentes con lead time más largo. El descenso discreto estocástico considera estas interdependencias y oportunidades de abastecimiento en paralelo.

Abastecimiento múltiple con restricciones

Ahora considera el reabastecimiento con múltiples restricciones y varias opciones de abastecimiento. Los proveedores imponen MOQs (cantidades mínimas de pedido), que pueden expresarse en unidades (para el pedido completo) o en términos monetarios (para el pedido total). Además, se debe optar por contenedores completos para reducir los costos de transporte. Los productos pueden obtenerse localmente—lo que conduce a lead times más cortos y MOQs más bajos, pero a costos unitarios más altos—o de proveedores lejanos, que ofrecen costos unitarios más bajos pero implican lead times más largos y MOQs más altos. Aunque la empresa puede pedir múltiples contenedores semanalmente, cualquier producto específico típicamente aparece en no más de un contenedor por mes.

La optimización estocástica—con el descenso discreto estocástico como la técnica habilitadora—aborda el hecho de que realizar un pedido hoy puede impedir hacer otro pedido para el mismo producto mañana. Ningún producto por sí solo justifica típicamente un contenedor completo, por lo que incluso los artículos más vendidos deben agruparse con otros. En consecuencia, si un artículo se agota inesperadamente mientras queda un inventario significativo de la mayoría de los productos elegibles para el paquete, no existe una opción rentable para reordenar ese artículo específico de manera anticipada. El proceso de optimización evalúa las ramificaciones a largo plazo de cada pedido—como la programación de un contenedor completo—y tiene en cuenta cuánto tiempo pasará hasta que todos los productos involucrados puedan reabastecerse de nuevo factiblemente bajo las mismas restricciones.