Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Resumo Técnico: Características Geométricas de Subproblemas em Busca de Vizinhança Ampla Assistida por Máquinas de Ising

Definição do Problema
Problemas de otimização combinatória restritos de larga escala, como o Problema de Roteamento de Veículos (VRP), frequentemente exigem formulações de Otimização Binária Não Restrita Quadrática (QUBO) que excedem os limites de tamanho de entrada das máquinas de Ising atuais ou que sofrem com a degradação da qualidade da solução à medida que o número de variáveis binárias aumenta. Embora a Busca de Vizinhança Ampla (LNS) mitigue isso ao otimizar sequencialmente subproblemas restritos, as abordagens existentes tratam primariamente o número de variáveis binárias como o único parâmetro de controle. Os autores postulam que o número de variáveis isoladamente é insuficiente para caracterizar um subproblema; diferentes regras de construção podem gerar estruturas internas, relações de restrição e distribuições geométricas distintas, mesmo quando as contagens de variáveis são idênticas. A questão central é se a regra de construção do subproblema afeta o processo de otimização sequencial quando o tamanho do subproblema (número de variáveis binárias) é mantido fixo.

Metodologia
O estudo investiga essa questão utilizando o VRP como campo de teste, comparando duas regras distintas de construção de subproblemas dentro de uma estrutura de LNS assistida por máquina de Ising:

1. LNS-K (Baseada na Estrutura de Rotas): Este método constrói subproblemas baseados nas unidades semânticas do VRP. Ele seleciona um subconjunto de veículos ($K'$) da solução atual e inclui todos os clientes visitados por esses veículos. As variáveis do subprobleso correspondem às rotas dos veículos selecionados e seus respectivos clientes.
2. LNS-Q (Baseada em Variáveis QUBO): Este método constrói subproblemas baseados na representação QUBO. Ele seleciona um subconjunto de variáveis binárias ativas ($n'$) da solução atual como "âncoras" e inclui todas as variáveis envolvidas nas restrições associadas a essas âncoras. Esta abordagem opera no nível da representação, em vez de operar no nível do domínio do problema.

Os autores utilizaram duas máquinas de Ising: a D-Wave Advantage 4.1 (recozimento quântico) para instâncias de pequena escala ($N=5, 6, 7$) e a Fixstars Amplify AE (baseada em GPU) para instâncias de larga escala ($N=100, 200, 300, 400$).

O protocolo experimental envolveu duas comparações principais:

• LNS vs. Abordagem Ingênua: Comparando a LNS sequencial contra uma submissão única (single-shot) do QUBO completo, com tempo de recozimento total correspondente.
• LNS-K vs. LNS-Q: Uma comparação de "tamanho correspondente" (matched-size), onde os parâmetros $K'$ e $n'$ foram ajustados para que ambos os métodos gerassem subproblemas com exatamente o mesmo número de variáveis binárias.

As métricas principais incluíram a distância total da solução, a trajetória de melhoria iterativa e a variância de posição do conjunto de clientes selecionados (uma medida da dispersão espacial dos clientes incluídos no subproblema).

Principais Resultados

1. Eficácia da Otimização Sequencial: Sob orçamentos de tempo de recozimento total correspondentes, a LNS superou consistentemente a abordagem ingênua (QUBO completo de disparo único) em ambas as plataformas de hardware e tamanhos de problema. A LNS manteve soluções viáveis durante todo o processo e alcançou distâncias totais significativamente menores, particularmente para instâncias maiores ($N=400$).
2. Impacto das Regras de Construção: Mesmo quando o número de variáveis binárias nos subproblemas foi estritamente igualado, a LNS-K e a LNS-Q exibiram comportamentos de otimização distintos.
   • Qualidade da Solução Final: A LNS-K alcançou distâncias totais finais mais curtas do que a LNS-Q através das faixas de parâmetros testadas para a instância de 400 clientes.
   • Trajetórias Iterativas: A LNS-K demonstrou uma melhoria iterativa mais rápida, particularmente para tamanhos de subproblema correspondentes menores ($K'=2, 3$).
3. Evolução Geométrica: Um achado crítico diz respeito à distribuição espacial dos clientes selecionados.
   • Na LNS-K, a variância de posição do conjunto de clientes selecionados diminuiu significativamente durante as iterações, indicando que o algoritmo focou progressivamente em clusters de clientes mais espacialmente localizados conforme a solução melhorava.
   • Na LNS-Q, a variância de posição permaneceu quase constante ao longo das iterações, independentemente do tamanho do subproblema.

Significância e Alegações
O artigo afirma que o número de variáveis binárias é um descritor insuficiente para subproblemas em otimização sequencial assistida por máquinas de Ising. O estudo demonstra que a própria regra de construção — especificamente, se as variáveis são agrupadas por unidades semânticas do domínio do problema (rotas) ou por relações de restrição QUBO — molda fundamentalmente a trajetória de otimização e a qualidade da solução final.

Os autores argumentam que o design de subproblemas deve considerar não apenas o tamanho, mas também a estrutura semântica e geométrica herdada da solução atual. A performance superior da LNS-K sugere que preservar a estrutura de rotas da solução atual permite que o algoritmo explore a localidade espacial, levando a rearranjos locais mais eficazes.

Limitações e Escopo
Os autores explicitamente observam algumas limitações:

• As conclusões são específicas para as instâncias de VRP testadas e para a formulação QUBO particular utilizada.
• A análise geométrica é descritiva; o artigo não estabelece um elo causal entre a diminuição da variância de posição e a melhoria na distância total, nem afirma que a localização espacial seja a única causa do sucesso da LNS-K.
• A comparação detalhada da estrutura foi realizada primariamente na plataforma Fixstars Amplify AE; os resultados não são alegados como sendo independentes de hardware.
• O estudo não fornece um benchmark abrangente contra heurísticas clássicas de roteamento de veículos de última geração, focando em vez disso nos mecanismos internos da LNS assistida por máquina de Ising.

Em conclusão, o artigo postula que o design de subproblemas eficaz para máquinas de Ising requer a integração de informações estruturais da solução atual, indo além de simples restrições de contagem de variáveis.