Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization

Resumo Técnico: Melhoria de Desempenho do Algoritmo de Benders Híbrido Quântico-Clássico para Otimização de MILP

Enunciado do Problema
Problemas de programação linear de números inteiros mistos (MILP) são onipresentes na otimização industrial, particularmente no planejamento de sistemas de energia, mas frequentemente excedem os limites de tempo práticos dos solvers clássicos à medida que o tamanho dos problemas aumenta. Embora os recozedores quânticos (QAs) ofereçam um caminho potencial para acelerar a solução de instâncias de Otimização Binária Quadrática Não Restrita (QUBO), as limitações atuais do hardware — especificamente contagens restritas de qubits, restrições de conectividade e a natureza heurística dos solvers — impedem soluções quânticas autônomas para problemas de grande escala. Além disso, o overhead computacional necessário para "incorporar" (embed) os grafos lógicos de problemas nos grafos de hardware quântico físico constitui um gargalo significativo em abordagens híbridas. Este trabalho aborda o desafio de resolver problemas MILP desenvolvendo uma estrutura híbrida quântica-clássica que aproveita os QAs para o componente inteiro, mitigando simultaneamente os overheads de incorporação e problemas de precisão.

Metodologia
Os autores propõem um algoritmo de Decomposição de Benders (BD) agnóstico ao hardware onde o Problema Mestre (MP), contendo todas as variáveis inteiras, é reformulado como um QUBO e resolvido usando um recededor quântico (especificamente o D-Wave Advantage System 5.4). O Subproblema (SP), contendo variáveis contínuas, é resolvido classicamente. O algoritmo itera entre o MP e o SP, gerando cortes de Benders para refinar a região viável até a convergência.

As adaptações metodológicas principais incluem:

1. Reformulação QUBO: O componente inteiro do MP é transformado em um QUBO. Isso envolve a discretização da variável contínua $\alpha$ (representando o limite inferior da contribuição contínua) e a introdução de variáveis de folga para converter restrições de desigualdade em igualdades. Os autores empregam arredondamento inteiro conservador para os limites dos cortes a fim de minimizar o número de variáveis de folga e qubits necessários.
2. Estratégias de Incorporação (Embedding): Para abordar o alto custo computacional de incorporação, o estudo compara três estratégias:
   • Minorminer (MM): A heurística padrão da D-Wave, que computa as incorporações dinamicamente para cada iteração.
   • Fixa (FX): Utiliza uma incorporação pré-computada de um grafo completo de 160 nós para todas as iterações.
   • Mais Justa (TT - Tightest): Usa um grafo completo pré-computado que corresponde ao tamanho específico do QUBO na iteração atual.
3. Critérios de Parada e Precisão: O algoritmo termina quando a lacuna entre os limites superior e inferior está dentro de uma tolerância de 5% ou quando o tamanho do QUBO excede o limite do hardware (160 variáveis). O estudo reconhece que soluções heurísticas de QA não garantem a otimalidade global e que erros de arredondamento nos coeficientes dos cortes podem levar a iterações redundantes.

Principais Contribuições
O artigo apresenta várias contribuições específicas para o campo da otimização híbrida quântica-clássica:

• Estrutura Algorítmica: Um algoritmo BD-QA automatizado, baseado em Python, que integra o QA diretamente no processo de resolução do MP, distinguindo-se de abordagens que usam QAs apenas para seleção de cortes.
• Aceleração de Incorporação: A introdução de estratégias de incorporação pré-computadas (FX e TT) ao fluxo de trabalho BD-QA. Alega-se que este é o primeiro estudo a incorporar tais técnicas de aceleração na etapa de incorporação de um algoritmo BD-QA, reduzindo significativamente o tempo de pré-processamento.
• Análise Abrangente: Uma enumeração e análise detalhada de todos os passos do processo BD-QA, indo além de tratar o recededor como uma "caixa preta". Isso inclui o tratamento específico de restrições de corte, precisão de variáveis e escalonamento de peso de penalidade.
• Suíte de Benchmarking: A geração de um conjunto escalável de instâncias de Planejamento de Expansão de Rede de Transmissão (TNEP) (formulação Greenfield) derivadas do dataset PyPSA-EUR, adequadas para testes em hardware quântico limitado.

Resultados
O algoritmo proposto foi testado contra solvers clássicos (Gurobi) e uma abordagem de Simulated Annealing (SA) usando instâncias de TNEP variando de 3 a 15 barras.

• Qualidade da Solução: A abordagem híbrida alcançou soluções dentro da margem de aceitação de 5% da solução ótima clássica para tamanhos de problema de até 8 barras (usando incorporações FX/TT), comparado a 7 barras para a incorporação padrão Minorminer.
• Desempenho e Escalabilidade: O uso de incorporações pré-computadas (FX e TT) reduziu o tempo total de execução em aproximadamente uma ordem de magnitude em comparação com a abordagem dinâmica Minorminer, principalmente ao eliminar o tempo de computação de incorporação em cada iteração.
• Comportamento de Iteração: Ao contrário dos solvers clássicos onde as contagens de iteração tipicamente aumentam com o tamanho do problema, a natureza heurística do QA resultou em um número de iterações relativamente estável através de diferentes tamanhos de problema. No entanto, o tamanho do QUBO cresceu a cada iteração devido ao acúmulo de variáveis de folga para novos cortes.
• Complexidade: A análise empírica sugere que o tempo total de execução para a abordagem BD-QA escala linearmente com o número de iterações e leituras, enquanto os solvers exatos clássicos exibem tendências de escalonamento não lineares (potencialmente exponenciais).

Significância e Alegações
O artigo posiciona este trabalho como um passo para tornar o hardware quântico atual praticamente útil para otimização de grande escala, abordando os gargalos específicos de algoritmos híbridos. Os autores alegam que sua abordagem demonstra que:

1. Incorporações pré-computadas são uma otimização crítica para algoritmos híbridos, reduzindo substancialmente o overhead de pré-processamento sem comprometer a qualidade da solução.
2. Aplicação direta de QA ao Problema Mestre é viável para estruturas MILP decomponíveis específicas, desde que as estratégias de incorporação e o tratamento de cortes sejam cuidadosamente gerenciados.
3. Abordagens híbridas oferecem uma alternativa promissora para problemas onde os solvers clássicos enfrentam dificuldades com complexidade discreta, embora o hardware atual limite a escala dos casos solucionáveis.

Os autores mantêm-se modestos quanto à superioridade imediata da abordagem quântica, observando que os solvers clássicos (Gurobi) ainda superam o método híbrido na formulação original completa devido a técnicas de aceleração proprietárias indisponíveis no cenário decomposto. Eles concluem que, embora os resultados atuais sejam promissores, pesquisas adicionais são necessárias em estratégias de geração de cortes, adaptação dinâmica de parâmetros e regras de seleção de solução mais robustas para realizar plenamente o potencial do BD-QA em instâncias do mundo real de maior escala.