Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization

Este artigo propõe o algoritmo MaxCOSD para resolver problemas de controle de inventário de múltiplos produtos com demandas não independentes e dinâmicas complexas, oferecendo garantias teóricas de desempenho sob condições de não degenerescência.

O essencial

Imagine que você é o gerente de um grande supermercado. Sua tarefa diária é decidir quanto de cada produto (de arroz a iogurte) você deve pedir para o estoque.

Se você pedir de menos, perde vendas e clientes ficam bravos (custo de "falta"). Se pedir de mais, o produto estraga ou ocupa espaço caro no armazém (custo de "excesso"). O grande desafio é que você não sabe exatamente quantas pessoas vão comprar amanhã.

O Problema Antigo: A Adivinhação Perfeita

Antes, os especialistas em estoque diziam: "Para resolver isso, precisamos assumir que as compras de hoje são exatamente iguais às de ontem e de amanhã, e que tudo é perfeitamente previsível". Eles usavam modelos matemáticos que funcionavam bem em laboratórios, mas falhavam na vida real, onde o clima muda, tendências surgem e produtos estragam.

A Solução Nova: O "MaxCOSD"

Este artigo apresenta uma nova maneira de pensar e um novo algoritmo chamado MaxCOSD. Pense nele como um gerente de estoque superinteligente que aprende na marra, sem precisar de previsões mágicas.

Aqui está a explicação usando analogias do dia a dia:

1. O Jogo do "Tente e Erre" (Aprendizado Online)

Imagine que você está jogando um videogame difícil onde o mapa muda a cada segundo.

• O jeito antigo: Você tentava memorizar um mapa fixo (assumindo que o jogo é sempre igual). Quando o jogo mudava, você perdia.
• O jeito novo (MaxCOSD): Você joga, vê onde errou, ajusta sua rota e continua. O algoritmo não precisa saber o futuro; ele apenas reage ao que acontece agora e aprende com os erros passados para não repetir o mesmo erro amanhã.

2. O Desafio do "Produto que Estraga" (Dinâmica de Estado)

Aqui está a parte complicada que a maioria dos algoritmos antigos ignorava:

• Cenário Simples: Você vende um jornal. Se não vender hoje, ele vai para o lixo. Amanhã você começa do zero. É fácil.
• Cenário Real (Estoque com Estado): Você vende iogurte. Se sobrar iogurte hoje, ele fica no armazém amanhã, mas envelhece um dia. Se você pedir muito hoje, o iogurte de hoje pode estragar amanhã.
• O Pulo do Gato: O algoritmo MaxCOSD é especial porque ele entende que o que sobra hoje afeta o que você pode fazer amanhã. Ele não trata cada dia como um novo começo; ele leva em conta o "peso" do estoque anterior.

3. A Regra de Ouro: "Não deixe o estoque zerar"

O artigo descobre uma regra fundamental para que esse aprendizado funcione: os clientes precisam comprar algo.

• A Analogia: Imagine que você está tentando aprender a dirigir olhando para a estrada. Se a estrada estiver vazia (sem carros/demanda), você não aprende nada sobre como virar ou frear. Se a demanda for zero o tempo todo, o algoritmo não consegue "sentir" se pediu demais ou de menos.
• A Condição: O algoritmo exige que, de vez em quando, haja uma demanda mínima (pessoas comprando). Se ninguém comprar nada, é impossível aprender a gerenciar o estoque. O artigo prova matematicamente que, sem essa "mínima movimentação", é impossível ter um gerente perfeito.

4. Como o MaxCOSD funciona na prática?

Em vez de mudar a quantidade de pedidos todos os dias (o que poderia causar caos no armazém), o MaxCOSD funciona em ciclos:

1. Ele faz um pedido e mantém esse nível por um tempo.
2. Ele observa o que aconteceu (quanto vendeu, quanto sobrou).
3. Ele calcula um "novo nível ideal" baseado nos erros passados.
4. O Teste de Segurança: Antes de mudar o pedido, ele pergunta: "Se eu mudar para esse novo nível, vou conseguir entregar o que prometi?"
   • Se a resposta for SIM, ele muda.
   • Se a resposta for NÃO (porque o estoque atual é muito baixo para suportar a mudança), ele não muda e espera mais um pouco.

Isso garante que ele nunca cometa um erro que deixe o cliente sem produto (quebra de estoque), algo que outros algoritmos mais agressivos faziam.

Resumo da Ópera

Este paper diz: "Pare de tentar prever o futuro com modelos rígidos. Use um sistema que aprende com os erros, entende que o estoque de hoje afeta o de amanhã, e só muda de estratégia quando tem certeza de que não vai deixar o cliente na mão."

O resultado? Um gerente de estoque que, mesmo em um mundo caótico e imprevisível, consegue reduzir drasticamente o dinheiro perdido com produtos estragados ou vendas perdidas, sem precisar de supercomputadores ou previsões mágicas. É como ter um assistente que aprende a dirigir no trânsito pesado e nunca bate no carro da frente.

Resumo técnico

Resumo Técnico: Problemas de Inventário Online Além do Cenário i.i.d. com Otimização Convexa Online

1. O Problema

O artigo aborda o problema de controle de inventário online para múltiplos produtos. O objetivo de um gestor de inventário é tomar decisões sequenciais de reabastecimento (definir níveis de estoque) para minimizar as perdas cumulativas (custos de armazenamento e perda de vendas) ao longo do tempo.

O trabalho identifica limitações críticas na literatura existente:

• Suposições Irrealistas: A maioria dos modelos assume que a demanda é independente e identicamente distribuída (i.i.d.), ignorando correlações e não-estacionariedades comuns no mundo real.
• Estruturas de Custo e Dinâmica Restritas: Muitos trabalhos focam apenas em custos do tipo "Newsvendor" (vendedor de jornais) e dinâmicas de inventário específicas (como produtos não perecíveis com vendas perdidas ou atrasadas), excluindo cenários complexos como perecibilidade ou dinâmicas com estado (stateful).
• Falta de Garantias Teóricas: Métodos anteriores frequentemente forneciam garantias fracas ou nenhuma garantia para cenários com demanda não-i.i.d. e dinâmicas complexas.

O objetivo central é desenvolver um algoritmo que funcione sob demandas gerais (não necessariamente i.i.d.), funções de perda gerais e dinâmicas de inventário complexas (incluindo perecibilidade), mantendo garantias teóricas rigorosas.

2. Metodologia e Modelo

2.1. Novo Framework: OIO (Online Inventory Optimization)
Os autores propõem um novo framework chamado OIO, que estende a Otimização Convexa Online (OCO).

• Protocolo: Em cada período $t$, o gestor observa o estado atual do inventário $x_t$, escolhe um nível de reabastecimento $y_t$ (sujeito a $y_t \succeq x_t$), sofre uma perda $\ell_t(y_t)$ e observa um subgradiente $g_t$. O ambiente atualiza o estado para $x_{t+1}$ baseado em uma dinâmica que pode incluir perecibilidade, vendas perdidas ou atraso de pedidos.
• Assunções Gerais: O conjunto viável $Y$ é convexo e limitado; as funções de perda são convexas com subgradientes limitados.
• Diferença Crítica: Diferente do OCO padrão, no OIO a viabilidade da decisão ($y_t \succeq x_t$) depende do histórico e da demanda, tornando o problema mais complexo.

2.2. O Algoritmo: MaxCOSD
A contribuição principal é o algoritmo MaxCOSD (Maximum Cyclic Online Subgradient Descent).

• Mecanismo: É uma variante do Descida de Subgradiente Online (OSD). Em vez de atualizar o nível de estoque a cada período, o MaxCOSD opera em ciclos.
• Atualização Cíclica: Durante um ciclo $T_k$, o nível de estoque permanece constante ($y_t = y_{t_k}$). O algoritmo calcula um candidato de atualização $\hat{y}_{t+1}$ usando um passo de subgradiente com taxas de aprendizado adaptativas (inspiradas no AdaGrad-Norm).
• Gatilho de Atualização: Uma atualização real ocorre apenas se o novo candidato for viável em relação ao estado de inventário atual ($x_{t+1} \preceq \hat{y}_{t+1}$). Se não for viável, o nível atual é mantido.
• Taxas de Aprendizado Adaptativas: Utiliza taxas que dependem da norma acumulada dos subgradientes, permitindo adaptação sem necessidade de conhecer constantes de Lipschitz a priori.

2.3. Assunção de Não-Degenerescência
Para garantir o aprendizado em sistemas com estado (stateful), os autores introduzem uma hipótese de não-degenerescência na demanda (Assunção 10):

• A demanda deve ser "uniformemente provável positiva". Ou seja, existe uma probabilidade $\mu > 0$ de que a demanda em qualquer período seja maior que um limiar $\rho > 0$, independentemente do histórico passado.
• Esta assunção generaliza condições usadas em trabalhos anteriores (como $E[d] > 0$) mas não exige i.i.d.

3. Contribuições Principais

1. Algoritmo MaxCOSD: O primeiro algoritmo com garantias teóricas ótimas para problemas de inventário online com dinâmicas gerais (incluindo perecibilidade) e demandas não-i.i.d.
2. Garantias de Regret Ótimas: O algoritmo atinge uma taxa de regret de $O(\sqrt{T})$ (tanto em expectativa quanto com alta probabilidade), que é ótima para problemas convexos online.
3. Generalização: O método funciona para:
   • Demandas determinísticas, estocásticas, correlacionadas e não-estacionárias.
   • Dinâmicas de inventário complexas (perecíveis, vendas perdidas, atraso de pedidos).
   • Múltiplos produtos com restrições de capacidade.
4. Prova de Necessidade da Não-Degenerescência: Os autores provam teoremas (Proposições 13 e 14) mostrando que, sem uma hipótese de demanda não-degenerada (afastada de zero), é impossível alcançar regret sublinear em problemas de inventário com estado. Isso formaliza a intuição de que "demanda zero" impede a correção de erros de estoque.
5. Conexão Teórica: Estabelece uma ponte rigorosa entre a teoria de Otimização Convexa Online e a literatura de gestão de inventário, mostrando que o OIO é uma extensão estrita do OCO.

4. Resultados

• Teóricos: O Teorema 12 estabelece que, sob as assunções de convexidade, limitação e não-degenerescência da demanda, o MaxCOSD garante:
  $$E[R_T] \leq C \cdot \sqrt{T}$$
  onde $C$ depende das constantes do problema (diâmetro do conjunto, limite do gradiente, parâmetros de não-degenerescência).
• Numéricos: Experimentos foram realizados em 5 cenários:
  1. Vendas perdidas (single-product, i.i.d.).
  2. Perecibilidade (single-product, i.i.d.).
  3. Multi-product com restrições de capacidade (i.i.d.).
  4. Multi-product com dados reais (M5 Competition, não-i.i.d.).
  5. Multi-product com dados reais e restrições de caixa (box constraints).
  • Desempenho: O MaxCOSD superou ou igualou algoritmos de base (AIM, CUP, DDM) em cenários de pequeno e médio porte.
  • Limitação Empírica: Em cenários com número muito alto de produtos ($n=3049$) e dados reais não-i.i.d., o desempenho do MaxCOSD degradou-se em comparação a métodos heurísticos, pois a probabilidade de satisfazer a condição de viabilidade para atualizações diminui conforme $n$ cresce (o "gargalo" da viabilidade).

5. Significado e Conclusão

Este trabalho é significativo por romper com a barreira das suposições i.i.d. na literatura de inventário online.

• Para a Indústria: Oferece um método robusto para ambientes de demanda volátil e correlacionada, onde modelos tradicionais falham.
• Para a Pesquisa: Demonstra que técnicas modernas de aprendizado online (como taxas adaptativas e análise de ciclos) podem ser aplicadas a problemas de controle com restrições dinâmicas complexas.
• Limitações e Futuro: O artigo aponta que, embora o MaxCOSD seja teoricamente sólido, sua eficiência prática em grandes dimensões (muitos produtos) pode ser melhorada com projeções mais sofisticadas nas restrições de viabilidade. Além disso, a hipótese de não-degenerescência, embora necessária, pode ser relaxada em futuras pesquisas.

Em suma, o paper fornece a primeira solução algorítmica com garantias de regret ótimo para uma classe ampla e realista de problemas de gestão de inventário, validando a utilidade da Otimização Convexa Online fora do domínio acadêmico restrito do i.i.d.