Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Resumo Técnico: Busca de Vizinhança Ampla Assistida por Máquina de Ising com Tamanho de Subproblema Flexivelmente Ajustável

Definição do Problema
As máquinas de Ising servem como resolvedores heurísticos para otimização combinatória ao buscar estados de baixa energia de modelos de Ising ou de Otimização Binária Não Constrangida Quadrática (QUBO). No entanto, aplicar essas máquinas diretamente a problemas restritos de grande escala (o "método ingênuo") enfrenta duas dificuldades primárias:

1. Escalabilidade: O número de variáveis binárias na formulação QUBO frequentemente excede a capacidade de hardware das máquinas de Ising atuais.
2. Viabilidade: As restrições são tipicamente incorporadas como termos de penalidade. Consequentemente, o espaço de busca inclui soluções inviáveis, e estados de baixa energia não correspondem necessariamente a soluções viáveis de alta qualidade do problema original.

Embora abordagens existentes, como o fixamento de variáveis ou o divide-e-conquista, tentem reduzir o tamanho do problema, elas frequentemente lutam para equilibrar o tamanho do subproblema com a capacidade de reconstruir soluções viáveis para o problema original. A Busca de Vizinhança Ampla (LNS) oferece uma estrutura onde uma solução atual viável é iterativamente melhorada reotimizando um subproblema (uma "vizinhança"). Enquanto a LNS preserva a viabilidade se o método de geração do subproblema for projetado corretamente, o desempenho da LNS assistida por máquina de Ising é altamente sensível ao tamanho do subproblema. Se o subproblema for muito pequeno, o potencial de melhoria por iteração é limitado; se for muito grande, a qualidade da solução da máquina de Ising degrada-se devido ao espaço de busca expandido.

Metodologia
O artigo foca em dois problemas: o Problema de Roteamento de Veículos (VRP) e o Problema de Múltiplas Mochilas Quadrático (QMKP).

• Método Existente (LNS-V): Para o VRP, os autores analisam um método anterior (LNS-V) que seleciona um subconjunto de veículos e reotimiza suas rotas inteiras. Embora isso preserve a viabilidade, o tamanho do subproblema é controlado apenas pelo número de veículos selecionados ($V'$). Como a rota inteira de um veículo selecionado é reotimizada, o número de variáveis escala como $(V')^2(T-2)^2$ (onde $T$ é o total de etapas). Isso resulta em uma granularidade grosseira; alterar $V'$ em um pode causar um salto massivo na contagem de variáveis, tornando difícil ajustar o tamanho do subproblema para a faixa ideal para a máquina de Ising.

• Método Proposto (LNS-VT): Para abordar o problema da granularidade, os autores propõem o LNS-VT. Além de selecionar $V'$ veículos, o LNS-VT introduz um novo parâmetro: o número de etapas consecutivas ($T'$) a serem reotimizadas para cada veículo selecionado.

  • Mecanismo: Para cada veículo selecionado, um segmento contíguo da rota (de comprimento $T_{seg} = \min(T', \text{etapas válidas reais})$) é extraído. O subproblema reotimiza a atribuição e a ordem dos locais dentro desses segmentos específicos, mantendo o restante da rota fixo.
  • Viabilidade: Ao fixar os locais fora dos intervalos de extração e garantir que os segmentos extraídos envolvam apenas locais que não sejam depósitos, o método garante que a reinserção de qualquer solução viável do subproblema resulte em uma solução viável para o VRP original.
  • Controle de Variáveis: O número de variáveis livres no LNS-VT é aproximadamente $(V'T')^2$. Isso permite um controle de granularidade fina sobre o tamanho do subproblema, independente do total de etapas do problema $T$.

• Extensão para QMKP: Os autores aplicam o mesmo princípio de design ao QMKP. Eles constroem um método de geração de subproblema que seleciona um subconjunto de mochilas ($K'$) e um subconjunto de itens ($N'$) para reotimização. Este método também preserva a viabilidade ao fixar itens que não estão no conjunto selecionado e ajustar as restrições de capacidade para a capacidade residual das mochilas selecionadas.

Resultados Principais
Experimentos numéricos foram conduzidos para um VRP de 300 locais e 5 veículos, e um QMKP de 200 itens e 5 mochilas, utilizando a máquina de Ising Fixstars Amplify AE.

• Desempenho do VRP:

  • O LNS-VT superou tanto o método ingênuo quanto o LNS-V existente.
  • A melhor configuração do LNS-VT (especificamente $V'=2, T'=40$) reduziu o valor objetivo em aproximadamente 10% em relação ao Ls-V após 100 iterações.
  • O LNS-VT atingiu a qualidade de solução final do LNS-V usando apenas cerca de 30% das iterações.
  • Sensibilidade de Variáveis: O tamanho ideal do subproblema (em termos de variáveis de atribuição de locais não-depósito) foi encontrado entre 6.000 e 10.000. O LNS-V existente não conseguiu atingir essa faixa com $V' \ge 2$ (seu mínimo era de ~14.400 variáveis), explicando seu desempenho inferior.
  • Necessidades Dinâmicas: O tamanho apropriado do subproblema mudou durante o processo de busca. Subproblemas maiores foram mais eficazes nas iterações iniciais (valores de objetivo altos), enquanto subproblemas menores foram mais eficazes nas iterações finais (refinando soluções de alta qualidade).

• Desempenho do QMKP:

  • A LNS aplicada ao QMKP também superou o método ingênuo.
  • O tamanho ideal do subproblema para o QMKP foi significativamente menor, aproximadamente 100 a 150 variáveis.
  • Essa diferença marcante em relação ao VRP (6.000–10.000) indica que o tamanho ideal do subproblema depende da classe específica do problema e da formulação QUBO, não apenas das capacidades da máquina de Ising.

Significância e Alegações
O artigo alega que, para que a LNS assistida por máquina de Ising seja eficaz para problemas restritos de grande escala, a preservação da viabilidade por si só é insuficiente. A capacidade de ajustar flexivelmente o tamanho do subproblema para coincidir com o ponto ideal de desempenho da máquina de Ising é um fator de design crítico.

O estudo demonstra que:

1. A introdução de um parâmetro de controle adicional (etapas consecutivas para VRP, ou contagem de itens/mochilas para QMKP) permite o ajuste de granularidade fina do tamanho do subproblema, o que é impossível com métodos que apenas variam o número de entidades selecionadas.
2. Existe uma faixa ótima de variáveis para o subproblema que maximiza a qualidade da solução, e essa faixa varia significativamente entre diferentes classes de problemas (VRP vs. QMKP).
3. O tamanho ideal do subproblema também pode depender da qualidade da solução atual, sugerindo que configurações de parâmetros estáticas podem não ser ideais ao longo de todo o processo de busca.

Os autores concluem que, embora seus resultados sejam específicos para as instâncias e configurações de máquina testadas, o princípio da geração de subproblemas baseada em estrutura e flexivelmente ajustável é uma direção promissora para a otimização combinatória restrita. Eles observam que trabalhos futuros devem focar no desenvolvimento de estratégias adaptativas para selecionar automaticamente os parâmetros do subproblema com base no estágio da busca e na estrutura do problema.