Evaluating the Performance of Direct Higher-Order Formulations in Combinatorial Optimization Problems

Resumo Técnico: Avaliando o Desempenho de Formulações Diretas de Ordem Superior em Problemas de Otimização Combinatória

Definição do Problema
Problemas de otimização combinatória são frequentemente encontrados em campos como logística, design de materiais e otimização de portfólio. Embora muitos desses problemas sejam NP-difíceis e exijam abordagens heurísticas, existe uma barreira significativa em sua implementação em "máquinas de Ising" (incluindo hardware de recozimento quântico e solvers inspirados em física). A maioria das plataformas de hardware existentes aceita entradas exclusivamente no formato de Otimização Binária Não Restrita Quadrática (QUBO), o que restringe as funções objetivo a termos lineares e quadráticos de variáveis binárias.

No entanto, inúmeros problemas do mundo real, como amostragem de polímeros, dobramento de proteínas e tarefas específicas de roteamento, envolvem inerentemente interações de ordem superior (cúbicas, quárticas, etc.). Para resolvê-los em hardware padrão, pesquisadores devem aplicar técnicas de "redução de ordem" para transformar problemas de Otimização Binária Não Restrita Polinomial (PUBO) para a forma QUBO. Esse processo introduz variáveis auxiliares e termos de penalidade para manter a consistência lógica. Os autores postulam que essa transformação inevitavelmente aumenta o tamanho do problema e a complexidade estrutural, podendo degradar a qualidade e a estabilidade da solução, embora o impacto específico de lidar diretamente com termos de ordem superior versus reduzi-los não tenha sido quantificado minuciosamente em uma plataforma unificada para instâncias práticas de grande escala.

Metodologia
Para abordar essa lacuna, o estudo utiliza um framework de avaliação comparativa usando o Fixstars Amplify Annealing Engine (Amplify AE). Este solver de alto desempenho, baseado em Simulated Annealing (SA) e paralelização GPU de larga escala, oferece dois modos distintos:

1. Solver PUBO: Otimiza diretamente funções objetivo contendo termos de até quarta ordem sem modificação.
2. Solver QUBO: Resolve os mesmos problemas após a aplicação do método de substituição para redução de ordem. Este método substitui produtos de variáveis binárias por novas variáveis auxiliares e impõe restrições via termos de penalidade (especificamente, $x_1x_2 = y_{1,2}$).

O estudo compara essas duas abordagens em dois problemas de referência que contêm naturalmente termos de ordem superior:

• Low Autocorrelation Binary Sequence (LABS): Um problema que busca sequências binárias com energia de autocorrelação mínima. A função de energia envolve termos de autocorrelação ao quadrado, resultando em interações de quarta ordem ($s_i s_{i+k} s_j s_{j+k}$).
• Problema de Roteamento de Veículos (VRP) com Balanceamento de Distância: Um problema multiobjetivo que minimiza a distância total de viagem enquanto minimiza simultaneamente a variância das distâncias entre os veículos. O termo de variância introduz interações de quarta ordem quando expandido.

Experimentos foram conduzidos com tempos computacionais fixos (60 segundos) através de vários tamanhos de problema. Para LABS, comprimentos de sequência ($N$) variaram de 5 a 99. Para VRP, o número de localizações de clientes ($P$) e veículos ($V$) foram variados. O solver QUBO utilizou um coeficiente de penalidade fixo ($p=1$) para o método de substituição, enquanto o solver PUBO não exigiu tal parâmetro de ajuste.

Principais Contribuições e Resultados
O artigo fornece uma análise quantitativa dos trade-offs entre a formulação direta PUBO e a formulação reduzida QUBO:

1. Qualidade e Estabilidade da Solução:

   • LABS: O solver PUBO alcançou consistentemente valores de energia normalizados mais baixos (mais próximos da solução ótima) com desvios padrão significativamente menores em comparação ao solver QUBO. A lacuna de desempenho aumentou conforme o comprimento da sequência $N$ aumentava.
   • VRP: Em análise de instância única, o solver PUBO produziu trade-offs mais estáveis entre distância total e variância de distância. Gráficos de dispersão revelaram que as soluções QUBO estavam amplamente dispersas e falharam em atingir a região de variância mínima real, enquanto as soluções PUBO se concentraram próximo à fronteira de Pareto.
   • Análise de Hipervolume: Em 30 instâncias de VRP geradas aleatoriamente, o solver PUBO alcançou consistentemente indicadores de hipervolume maiores (uma medida de diversidade e qualidade do conjunto de soluções) do que o solver QUBO, confirmando sua superioridade em otimização multiobjetivo.

2. Expansão de Variáveis:

   • O estudo quantificou a "explosão de variáveis" causada pela redução de ordem. Para ambos, LABS e VRP, o número de variáveis binárias na formulação QUBO cresceu rapidamente com o tamanho do problema, atingindo dezenas de vezes o número de variáveis na formulação direta PUBO para instâncias grandes. Essa expansão amplia o espaço de busca, contribuindo para a degradação observada na estabilidade da solução.

3. Sensibilidade aos Coeficientes de Penalidade:

   • Os autores investigaram a sensibilidade da abordagem QUBO ao coeficiente de penalidade ($p$) usado no método de substituição. Uma análise de mapa de calor para o problema LABS demonstrou que o coeficiente de penalidade ideal varia significamente com o tamanho do problema ($N$). Nenhum valor único de $p$ proporcionou desempenho consistente em todas as escalas, destacando a dificuldade de ajustar formulações reduzidas para aplicações gerais.

Significância e Alegações
O artigo afirma que lidar diretamente com termos de ordem superior via formulações PUBO oferece vantagens distintas sobre os métodos tradicionais de redução de ordem ao resolver problemas de otimização combinatória em hardware moderno do tipo Ising. A principal significância reside na demonstração de que:

• Integridade Estrutural: Preservar a estrutura original do problema (PUBO) evita a expansão artificial do espaço de busca causada por variáveis auxiliares.
• Robustez: A formulação direta elimina a necessidade de ajustar coeficientes de penalidade, que são sensíveis à escala do problema e podem desestabilizar o processo de busca.
• Escalabilidade: A abordagem PUBO mantém qualidade e estabilidade de solução superiores conforme os tamanhos dos problemas aumentam, enquanto a abordagem QUBO sofre com os efeitos compostos da expansão de variáveis e imposição de restrições.

Os autores concluem que, embora a redução de ordem tenha sido eficaz para vários problemas, a formulação direta PUBO representa uma abordagem promissora para cenários de otimização prática de grande escala, oferecendo tanto simplicidade estrutural quanto estabilidade computacional. O estudo sugere que o desenvolvimento futuro de hardware e solvers deve continuar a suportar a execução direta de ordem superior para aproveitar plenamente esses benefícios em aplicações do mundo real.