Learning to Cut: Reinforcement Learning for Benders Decomposition

Resumo Técnico: Aprendendo a Cortar: Aprendizado por Reforço para Decomposição de Benders

Declaração do Problema
A Decomposição de Benders (DB) é uma abordagem padrão para resolver programas estocásticos de dois estágios, que modelam a tomada de decisão sob incerteza separando decisões de primeira etapa "aqui-e-agora" de ações de recurso de segunda etapa "esperar-e-ver". Embora eficaz, a DB clássica frequentemente sofre de convergência lenta. Essa ineficiência surge de um trade-off no gerenciamento de cortes: adicionar todos os cortes por cenário (formulação multi-corte) cria uma aproximação mais apertada da função de recurso, mas aumenta significativamente o problema mestre, retardando as resoluções subsequentes; inversamente, agregar cortes em um único corte (formulação único-corte) mantém o problema mestre pequeno, mas produz aproximações mais fracas. Abordagens heurísticas existentes, como selecionar apenas os cortes mais violados ou utilizar cortes Pareto-ótimos, tentam gerenciar isso, mas frequentemente dependem de regras determinísticas que podem não se adaptar bem a estruturas de problema variáveis ou entradas de dados.

Metodologia
Os autores propõem Aprendizado por Reforço para DB (RLBD), um framework que modela a seleção de cortes como um problema de tomada de decisão sequencial dentro de um Processo de Decisão de Markov (MDP) de horizonte finito com desconto.

• Formulação do MDP:

  • Espaço de Estados ($S$): O estado em cada iteração $t$ captura estatísticas globais de convergência (índice de iteração, limites inferior/superior, lacuna de otimalidade, taxas de redução da lacuna e tempos de resolução do problema mestre/subproblema) e características locais dos cortes. Características locais para cada corte candidato incluem níveis de violação, normas de variáveis duais, coeficientes de corte e a frequência histórica de cortes gerados pelo mesmo cenário.
  • Espaço de Ações ($A$): A ação consiste em selecionar um subconjunto de $K$ cortes candidatos dos cortes por cenário disponíveis para adicionar ao problema mestre.
  • Função de Recompensa ($r$): A recompensa é uma soma ponderada de três componentes: (1) um termo baseado na lacuna refletindo a redução logarítmica na lacuna de otimalidade (incentivando a convergência), (2) um termo negativo proporcional ao tempo de resolução do problema mestre (incentivando a eficiência) e (3) uma penalidade por passo (incentivando trajetórias mais curtas).
  • Dinâmicas de Transição: O ambiente transita para o próximo estado resolvendo o problema mestre atualizado com os cortes selecionados, gerando novos subproblemas e computando novos limites e estatísticas.

• Parametrização da Política e Treinamento:

  • A política de seleção de cortes $\pi_\theta$ é parametrizada por uma rede neural feedforward compartilhada. A rede processa um vetor concatenado de informações de estado global e características locais de corte para cada corte candidato, produzindo um logit escalar. Uma função softmax converte esses logits em uma distribuição de probabilidade.
  • A política é treinada usando o algoritmo REINFORCE (um método de gradiente de política). Durante episódios de treinamento, o agente amostra uma sequência de $K$ cortes sem reposição com base na distribuição da política atual. Os parâmetros da política são atualizados via ascensão de gradiente para maximizar a recompensa descontada cumulativa esperada.
  • Inferência: Durante os testes, a política treinada é aplicada de maneira gulosa, selecionando os $K$ cortes principais com os logits mais altos para cada nova instância de problema.

Principais Contribuições

1. Política Estocástica de Seleção de Cortes: Diferentemente de heurísticas determinísticas, o RLBD emprega uma política estocástica que atribui probabilidades de seleção com base tanto no progresso algorítmico global quanto nas características locais dos cortes. Isso permite que o agente explore cortes informativos enquanto mantém a capacidade de explorar candidatos alternativos que podem se tornar críticos posteriormente.
2. Capacidade de Generalização: O framework é projetado para generalizar para problemas com estruturas similares, mas entradas de dados variáveis (por exemplo, diferentes realizações de demanda) e dimensões de variáveis de decisão (por exemplo, diferentes números de instalações ou clientes), sem necessidade de retreinamento.
3. Melhorias de Desempenho: A abordagem demonstra melhorias substanciais sobre benchmarks existentes, incluindo DB pura e LearnBD (uma abordagem de aprendizado supervisionado usando Máquinas de Vetor de Suporte).

Resultados Experimentais
Os autores avaliaram o RLBD em um problema de localização de estações de carregamento de veículos elétricos (VE) de dois estágios estocásticos. Os experimentos envolveram treinamento em uma instância específica e teste em instâncias com tamanhos de problema variados ($8\times12$, $10\times15$, $20\times30$) e distribuições de demanda (Normal, enviesada à esquerda e enviesada à direita).

• Instâncias Pequenas a Médias: Para instâncias com configurações $8\times12$ e $10\times15$, o RLBD alcançou uma redução no tempo computacional de aproximadamente cinco vezes em comparação com a DB pura e o LearnBD, mantendo lacunas de otimalidade comparáveis. Esse ganho de eficiência foi atribuído principalmente à seleção adaptativa de cortes, que resultou em tempos de resolução do problema mestre significativamente menores.
• Instâncias Grandes: Para instâncias maiores ($20\times30$) onde todos os métodos falharam em convergir dentro do limite de tempo de uma hora, o RLBD alcançou uma lacuna de otimalidade final menor (aprox. 28–29%) em comparação com os benchmarks (aprox. 35–39%).
• Sensibilidade a Hiperparâmetros: O estudo identificou que um peso de recompensa de $\alpha=0.01$ (redução da lacuna) e $\lambda=0.001$ (penalidade por passo), combinado com a adição de $K=10$ cortes por iteração, produziu a convergência e eficiência mais estáveis.
• Insights Gerenciais: A análise da política aprendida revelou que ela tende a priorizar cortes de cenários com maior demanda total, exposição a penalidades e exposição a receita, sugerindo que o modelo identifica com sucesso realizações de alta carga como críticas para apertar a formulação.

Significado e Alegações
O artigo afirma que o RLBD oferece uma alternativa robusta e adaptativa às estratégias tradicionais de gerenciamento de cortes. Ao enquadrar a seleção de cortes como um problema de aprendizado, o método supera a rigidez das heurísticas determinísticas. Os autores enfatizam que a política treinada exibe forte generalização, lidando efetivamente com deslocamentos de distribuição e mudanças nas dimensões do problema sem exigir retreinamento. Os resultados sugerem que integrar aprendizado por reforço ao loop de DB pode melhorar significativamente a eficiência computacional para programas estocásticos de dois estágios, particularmente em cenários onde o tamanho do problema mestre se torna um gargalo. O trabalho posiciona o RLBD como um método viável para melhorar a escalabilidade da otimização estocástica em aplicações do mundo real, como localização de instalações e gestão da cadeia de suprimentos.