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

Resumo Técnico: Um Método Computacional para Resolver o Problema de Reposição Conjunta Estocástica em Altas Dimensões

Formulação do Problema
O artigo aborda o Problema de Reposição Conjunta Estocástica (SJRP), um desafio clássico de gestão de estoques que envolve a coordenação de sistemas de inventário de múltiplos itens, onde um custo fixo de reposição é incorrido conjuntamente para itens pedidos juntos. Na formulação de tempo discreto considerada, um gestor de armazém revisa os níveis de inventário periodicamente e decide se deve realizar pedidos para subconjuntos de $d$ itens. O sistema enfrenta demandas aleatórias, custos de manutenção lineares e penalidades por atraso. O objetivo é minimizar o custo total esperado descontado ao longo de um horizonte infinito.

A dificuldade central reside na "maldição da dimensionalidade". Sob custos fixos de reposição não nulos, as decisões ao nível do item tornam-se interdependentes, fazendo com que os espaços de estado e decisão do Processo de Decisão de Markov (MDP) associado cresçam exponencialmente com o número de itens ($d$). Consequentemente, técnicas padrão de programação dinâmica tornam-se computacionalmente intratáveis para configurações de alta dimensão (por exemplo, $d \ge 50$), e a literatura existente tem dependido majoritariamente de políticas heurísticas com garantias teóricas limitadas de optimalidade.

Metodologia
Para superar essas barreiras computacionais, os autores propõem um método computacional inovador baseado em simulação que faz a ponte entre o controle de inventário de tempo discreto e a teoria de controle impulsivo de tempo contínuo e aprendizado profundo.

1. Aproximação de Tempo Contínuo: O SJRP de tempo discreto é aproximado por um problema de controle impulsivo de tempo contínuo. Nesta formulação, o processo cumulativo de demanda é modelado como um processo Gaussiano (movimento browniano com deriva), e o gestor pode intervir a qualquer momento para saltar instantaneamente o estado do inventário para um nível superior a um custo fixo. Esta aproximação permite uma representação probabilística da função de valor que é mais adequada para técnicas de solução de alta dimensão.

2. Representação Probabilística via EDPs Estocásticas Conjugadas (BSDEs) Conjugadas: Ao contrário dos métodos padrão de Equações Diferenciais Estocásticas Reversas (BSDE) profundas que dependem de igualdades quase certas, a função de valor deste problema de controle impulsivo é caracterizada como a solução mínima de uma BSDE conjugada. Isso leva a uma identidade estocástica envolvendo uma desigualdade quase certa em vez de uma igualdade. Especificamente, a função de valor $V(x)$ é o supremo dos valores $v$ que satisfazem uma condição de alvo estocástico envolvendo o processo de referência, os custos de funcionamento e os custos de salto.

3. Solver de Rede Neural Profunda: Os autores desenvolvem um algoritmo computacional para resolver esta BSDE conjugada utilizando redes neurais profundas.

   • Função de Perda: Uma nova função de perda é construída para lidar com a restrição de desigualdade. Ela inclui um termo de penalidade para violações da desigualdade estocástica, ponderado por um parâmetro de penalidade ajustável $\beta$.
   • Processo de Referência: Uma política de referência cuidadosamente projetada (uma política de "pedir até" aleatorizada impulsionada por um processo de Poisson) é utilizada para gerar trajetórias amostrais. Este processo é projetado para equilibrar exploração e exploração, garantindo que as redes neurais sejam treinadas em regiões relevantes do espaço de estados.
   • Estratégia de Treinamento: Para garantir estabilidade, os autores empregam um cronograma conjunto para o parâmetro de penalidade $\beta$ e a taxa de aprendizado. A penalidade é aumentada gradualmente enquanto a taxa de aprendizado é diminuída, permitindo que a rede primeiro aprenda a estrutura geral e depois imponha estritamente as restrições de desigualdade.

4. Extração de Política: Uma vez que a função de valor $V$ e seu gradiente $\nabla V$ são aproximados por redes neurais, uma política implementável é derivada. A política verifica uma condição de "não-ação" derivada da equação de Hamilton-Jacobi-Bellman (HJB). Se a condição for violada, um pedido é realizado. O vetor de "pedir até" é determinado minimizando a soma da função de valor aproximada e o custo de pedido, uma etapa que pode ser pré-calculada de forma eficiente.

Principais Contribuições

• Escalabilidade de Alta Dimensão: O método resolve com sucesso o SJRP para dimensões de até pelo menos 50 (50 SKUs), um regime onde soluções ótimas baseadas em MDP tradicionais são intratáveis.
• Design Inovador de Função de Perda: O artigo introduz uma função de perda específica e um cronograma de treinamento adaptados ao framework de BSDE conjugada exigido para controle impulsivo, abordando o desafio das desigualdades quase certas que os métodos padrão de BSDE profunda não tratam.
• Engenharia do Processo de Referência: O design do processo de referência com saltos dependentes do estado é destacado como uma inovação crítica para garantir treinamento eficiente e cobertura do espaço de estados relevante.
• Implementação: Os autores fornecem um pipeline completo, desde a aproximação do problema até a extração da política, incluindo estratégias detalhadas de ajuste de hiperparâmetros e resultados computacionais.

Resultados
A política proposta de Rede Neural (RN) foi avaliada em 43 problemas de teste nas dimensões 2, 12 e 50, com variabilidade de demanda variável (baixa, média, alta) e estruturas de custo variadas.

• Baixas Dimensões ($d=2$): A política RN foi comparada à política ótima verdadeira derivada via técnicas padrão de solução de MDP. Os resultados mostram que a política RN performa dentro de 1% do custo ótimo e rastreia de perto a geometria dos limites de decisão ótimos.
• Altas Dimensões ($d=12$ e $d=50$): Como as soluções ótimas são intratáveis, a política RN foi comparada a heurísticas de última geração: revisão periódica $(R, S)$, $(Q, S)$, híbrida $(R, Q, S)$, can-order e políticas independentes $(s, S)$.
  • Em 12 dimensões, a política RN igualou ou superou a melhor referência em todos os casos. Em configurações de variabilidade média e alta, ela frequentemente superou a melhor heurística por margens significativas (por exemplo, até 28% de melhoria sobre $(R, S)$ em casos específicos de alta variabilidade).
  • Em 50 dimensões, a política RN consistentemente venceu a melhor heurística disponível em todos os casos de teste, com lacunas de desempenho atingindo até 5,59%.
• Eficiência Computacional: O tempo de treinamento escala modestamente com a dimensão (por exemplo, ~4 horas para 50 dimensões em uma única GPU), evitando o crescimento exponencial típico de métodos baseados em grade.

Significado e Alegações
O artigo alega que seu método fornece uma abordagem computacionalmente viável para obter políticas quase ótimas para problemas de reposição conjunta estocástica de alta dimensão, um desafio de longa data na gestão de operações. Ao aproveitar o aprendizado profundo para resolver o problema subjacente de controle impulsivo de alta dimensão, os autores demonstram que é possível igualar ou superar o desempenho das melhores heurísticas existentes sem depender de suposições estruturais restritivas. Os autores notam que, embora o método seja atualmente aplicado ao SJRP com custos lineares e vetores de pedido sem restrições, o framework é generalizável para outros problemas de controle impulsivo, incluindo aqueles em engenharia financeira (por exemplo, gestão de fluxo de caixa) e cadeias de suprimentos com tempos de entrega ou vendas perdidas, embora essas extensões sejam deixadas para trabalhos futuros. O artigo enfatiza que a política proposta não é meramente uma heurística, mas uma aproximação orientada por dados do controle ótimo derivada de uma formulação probabilística rigorosa.