Random-Key Optimizer and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem

Resumo Técnico: Otimizador de Chaves Aleatórias e Linearização para o Problema de Empacotamento em Lotes Variáveis com Múltiplas Restrições Quadráticas (QMC-VSBPP)

1. O Problema: QMC-VSBPP

O artigo aborda o Problema de Empacotamento em Lotes Variáveis com Múltiplas Restrições Quadráticas (QMC-VSBPP), uma variante complexa e NP-difícil do clássico Problema de Empacotamento em Lotes (BPP). Diferentemente das versões tradicionais, o QMC-VSBPP incorpora três características principais:

• Múltiplas Dimensões de Capacidade: Os itens e os lotes (bins) possuem vetores de peso e capacidade em $d$ dimensões (ex: CPU e RAM em alocação de recursos de nuvem), onde a viabilidade exige que o item caia em todas as dimensões simultaneamente.
• Tipos de Lotes Heterogêneos: Existem múltiplos tipos de lotes, cada um com custos fixos e capacidades distintas.
• Custos Quadráticos de Interação: O modelo inclui penalidades (custos) quando pares específicos de itens são alocados em lotes diferentes, modelando latências de comunicação ou custos de separação entre recursos interdependentes.

O objetivo é minimizar o custo total, que é a soma dos custos dos lotes utilizados e das penalidades de separação de itens.

2. Metodologia Proposta

Os autores propõem duas abordagens complementares para avançar o estado da arte: uma modelagem exata linearizada e um metaheurístico híbrido.

A. Modelagem Matemática Linearizada

• O modelo original do QMC-VSBPP contém termos quadráticos na função objetivo (representando a interação entre itens em lotes diferentes).
• Os autores desenvolveram uma linearização exata substituindo o termo quadrático $x_{ij}(1 - x_{sj})$ por uma nova variável binária auxiliar $z_{ijs}$, acompanhada de restrições lineares que garantem a equivalência lógica.
• Benefício: Esta transformação permite o uso de solucionadores exatos de alta performance (como o Gurobi) para calcular limites inferiores (lower bounds) fortes, algo que era computacionalmente inviável com o modelo quadrático original em grande escala.

B. RKO-ACO (Otimizador de Chaves Aleatórias com Colônia de Formigas Contínua)
Para encontrar soluções de alta qualidade (limites superiores) em tempo computacional viável, foi desenvolvido o algoritmo RKO-ACO, que integra:

1. Framework RKO (Random-Key Optimizer): Opera no espaço contínuo, decodificando vetores de chaves aleatórias em soluções discretas viáveis. Isso desacopla o motor de busca das restrições específicas do problema.
2. ACO de Domínio Contínuo (ACOR): Adaptação do algoritmo de Colônia de Formigas para espaços contínuos, utilizando um arquivo de elite de soluções para guiar a geração de novas soluções através de distribuições Gaussianas.
3. Ajuste de Parâmetros via Q-Learning: Um agente de aprendizado por reforço (Q-learning) ajusta dinamicamente parâmetros do algoritmo (tamanho do arquivo, pressão de seleção, etc.) durante a execução para equilibrar intensificação e diversificação.
4. Busca Local e Pós-processamento:
   • Decodificação: Estratégias semi-greedy e baseadas em grafos para atribuir itens aos lotes.
   • Pós-processamento: Substituição de tipos de lotes por versões mais baratas viáveis e fusão de lotes (bin merging) para reduzir custos.
   • Busca Local (Nelder-Mead): Refinamento local no espaço contínuo e realocação de itens no espaço discreto para reduzir custos e penalidades.

3. Contribuições Principais

• Primeiros Limites Inferiores Exatos: A introdução do modelo linearizado permitiu, pela primeira vez na literatura, calcular limites inferiores rigorosos para o QMC-VSBPP usando solucionadores exatos.
• Novo Algoritmo Híbrido: O desenvolvimento do RKO-ACO, combinando a flexibilidade do RKO com a eficiência do ACO contínuo e o controle adaptativo via Q-Learning.
• Novos Recordes (Upper Bounds): O algoritmo propôs novas melhores soluções conhecidas para a grande maioria das instâncias de benchmark.
• Análise Comparativa Abrangente: Avaliação detalhada contra métodos exatos (Gurobi), heurísticas anteriores (VNS) e benchmarks da literatura.

4. Resultados Computacionais

Os experimentos foram realizados em 96 instâncias de benchmark (variando de 25 a 200 itens) com tempo limite de 3600s para métodos exatos e tempos menores para metaheurísticos.

• Desempenho do Modelo Linearizado:

  • Produziu limites inferiores significativamente mais apertados que o modelo quadrático original.
  • Conseguiu provar otimalidade em 4 instâncias pequenas ($n=25$), enquanto o modelo original não conseguiu provar otimalidade em nenhuma.
  • Para instâncias grandes ($n \ge 50$), ambos os modelos apresentaram grandes lacunas de otimalidade (acima de 50-90%), evidenciando a necessidade de metaheurísticas.

• Desempenho do RKO-ACO:

  • Supremacia sobre o Estado da Arte: O RKO-ACO superou consistentemente o algoritmo VNS (Variational Neighborhood Search) anterior e os resultados do Gurobi.
  • Taxa de Sucesso: Encontrou a Melhor Solução Conhecida (BKS) ou melhorou o limite superior em 95 de 96 instâncias.
  • Eficiência: Para instâncias de $n=25$ a $n=100$, encontrou a BKS em 100% dos casos. Para $n=200$, alcançou a BKS em 23 de 24 casos.
  • Estabilidade: A análise de desvios percentuais (ARPD e BRPD) mostrou que o algoritmo é altamente estável, com desvios médios próximos de zero ou negativos (indicando melhoria sobre o BKS anterior).
  • Análise de Ablação: Estudos mostraram que a remoção de componentes (Q-Learning, Nelder-Mead ou o uso de ACO puro) resultou em degradação de desempenho, confirmando a eficácia da integração completa.

5. Significado e Conclusão

Este trabalho estabelece um novo marco para o problema QMC-VSBPP. A principal conclusão é que a combinação de linearização matemática (para obter limites inferiores fortes e validar a qualidade das soluções) com metaheurísticas adaptativas baseadas em chaves aleatórias (para explorar o espaço de soluções complexas) é a abordagem mais eficaz para este tipo de problema de empacotamento quadrático.

Os resultados fornecem novos valores de referência (benchmarks atualizados) para a comunidade científica e demonstram a viabilidade de aplicar frameworks de otimização contínua (como RKO) a problemas combinatórios discretos complexos, especialmente quando integrados a mecanismos de aprendizado de máquina (Q-Learning) para auto-ajuste de parâmetros. O código e as instâncias foram disponibilizados publicamente para reprodutibilidade.