Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Resumo Técnico: Formulação em Rede de Tensores do Problema do Caixeiro Viajante e Variantes

Definição do Problema
O artigo aborda o Problema do Caixeiro Viajante (TSP) e várias de suas generalizações, incluindo o TSP Dependente do Tempo (TDTSP), o Problema de Realocação de Tarefas (JRP) e variantes envolvendo restrições de não repetição, regras de precedência, restrições de grupo e objetivos de gargalo. O TSP é definido como encontrar a rota mais curta que visita $N$ nós exatamente uma vez e retorna ao início, um problema conhecido como NP-difícil. Embora existam algoritmos exatos como Held-Karp ($O(N^2 2^N)$) e branch-and-bound, eles enfrentam complexidade exponencial que limita sua escalabilidade para casos industriais. Por outro lado, heurísticas (por exemplo, algoritmos genéticos, busca local) oferecem soluções aproximadas sem garantias de otimalidade. Os autores observam que algoritmos quânticos emergentes (QAOA, VQE) são atualmente limitados pelo ruído de hardware (era NISQ), motivando a exploração de técnicas clássicas que imitam propriedades de sistemas quânticos.

Metodologia
A contribuição central é uma formulação em rede de tensores (TN) que representa rotas candidatas como estados em um espaço de produto tensorial. O método opera através de três mecanismos primários:

1. Construção da Rede de Tensores:

   • Inicialização ('+'): Cria uma superposição uniforme de todas as possíveis atribuições de nós para cada passo de tempo.
   • Otimização ('S'): Aplica um operador de evolução no tempo imaginário $U = e^{-\tau C(\vec{y})}$, onde $\tau$ é um fator de amortecimento e $C(\vec{y})$ é o custo da rota. Isso suprime exponencialmente configurações de alto custo, análogo à busca pelo estado fundamental em sistemas quânticos.
   • Filtragem de Restrições ('F'): Introduz camadas de Operador Produto Matricial (MPO) para impor restrições. Para o TSP padrão, essas camadas atuam como filtros de contagem garantindo que cada nó apareça exatamente uma vez. Os filtros utilizam índices de ligação binários para rastrear se um nó específico foi visitado, implementando efetivamente a restrição do símbolo de Levi-Civita $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$.
   • Extração ('+'): Uma camada de traço soma as amplitudes para produzir pesos marginais.

2. Extração Marginal Sequencial:
   A solução é extraída iterativamente. Para um prefixo fixo da rota, o algoritmo calcula o peso marginal $Z_p(a; \tau)$ para cada nó candidato $a$ na próxima posição. No limite de $\tau \to \infty$ e aritmética exata, o nó que maximiza esse peso é garantido como parte de uma rota ótima (Proposição 3.2). O algoritmo seleciona o nó maximizador, atualiza o prefixo e repete até que a rota esteja completa.

3. Generalizações:
   O framework é adaptado para várias variantes do TSP modificando as camadas de filtro e evolução:

   • DNSNN (Número Diferente de Passos/Nós): Filtros permitem que nós apareçam entre $N^0$ e $N^f$ vezes.
   • NMTSP (Não-Markoviano): Usa MPOs de ordem superior para lidar com custos dependentes dos $K$ passos anteriores.
   • BTSP (Gargalo): Substitui a evolução de custo por uma camada que rastreia o custo máximo da aresta encontrado.
   • PTSP (Restrito por Grupo): Filtros impõem a visita de exatamente um nó por classe.
   • TSPP (Precedência): Projetores locais suprimem nós se seus predecessores necessários ainda não tiverem aparecido.
   • JRP (Realocação de Tarefas): Modelado como um problema de atribuição linear onde um estado "sem movimento" é repetível, e vagas específicas são únicas.

4. Aproximação e Complexidade:
   A contração exata da rede de tensores completa é exponencial, escalando como $O(\hat{N}^4 2^{\hat{N}})$ para contração densa por camada. Para abordar instâncias maiores, os autores propõem:

   • Ablação de Camadas: Aplicar apenas um subconjunto de camadas de restrição para reduzir a complexidade, tratando o resultado como uma heurística.
   • Contração Esparsa-Local: Explorar a natureza determinística e esparsa dos tensores de filtro locais para reduzir fatores polinomiais (por exemplo, de $O(\hat{N}^4 2^{\hat{N}})$ para $O(\hat{N}^3 2^{\hat{N}})$) sem alterar a escala exponencial.
   • Heurística de $\tau$ Finito: Usar precisão finita e $\tau$ finito para aproximar o limite de temperatura zero, reconhecendo que o contraste numérico e as degenerescências afetam a qualidade da solução.

Contribuições Principais

• Fórmula Marginal Explícita: Derivação de uma equação marginal em rede de tensores cujo limite de aritmética exata e temperatura zero identifica uma rota viável ótima via uma regra marginal sequencial.
• Codificação de Restrições: Definição de camadas MPO para restrições de contagem (não repetição) aplicáveis a vários problemas combinatórios.
• Framework de Generalização: Uma construção modular que adapta o formalismo TN para variantes do TSP (TDTSP, JRP, BTSP, etc.) alterando camadas tensoriais específicas.
• Implementação Heurística: Uma implementação de precisão finita e $\tau$ finito que funciona como uma heurística calibrada, com análise de seu comportamento em relação ao contraste numérico e degenerescência.

Resultados
O estudo experimental foca em instâncias pequenas e sintéticas ($N \in \{5, \dots, 12\}$) para validar a correção do método e seu comportamento numérico, em vez de reivindicar superioridade computacional sobre solucionadores especializados.

• Calibração: O parâmetro de tempo imaginário $\tau$ é dependente do tamanho. Uma varredura de calibração ($\tau \in \{1, \dots, 40\}$) melhorou significativamente a taxa de solução ótima de 55,56% (em $\tau=1$) para 95,56% no conjunto de avaliação.
• Comparação com Solucionadores: Em instâncias pequenas, o solucionador TN calibrado alcançou uma taxa de otimalidade de 95,24%, superando o greedy do NetworkX (26,67%) e o recozimento simulado (59,05%), mas ficando aquém da referência exata Held-Karp (100%).
• Ablação de Camadas: A remoção de camadas de restrição degradou a qualidade da solução, confirmando que o conjunto completo de filtros é necessário para alta precisão.
• Caso Industrial (JRP): Em uma prova de conceito para o Problema de Realocação de Tarefas da ONCE, o método TN produziu soluções com custos acumulados idênticos ao Azure Digital Annealer, diferindo apenas em casos degenerados onde múltiplas atribuições ótimas existem.

Significado e Reivindicações
Os autores declaram explicitamente modéstia quanto ao poder computacional do método. Eles não reivindicam uma vantagem computacional geral sobre solucionadores clássicos especializados (como Held-Karp, branch-and-cut ou algoritmos específicos para atribuição) para o TSP geral.

• Representação Formal: O trabalho é apresentado como uma "representação formal exata de tempo exponencial em aritmética" e uma "plataforma para aproximações e extensões controladas".
• Natureza Heurística: A implementação de $\tau$ finito é caracterizada como uma "heurística calibrada de precisão finita" cujo comportamento depende do contraste numérico e das degenerescências.
• Utilidade: O valor principal reside no framework modular de rede de tensores, que permite a integração sistemática de diversas restrições (precedência, grupos, custos não-Markovianos) e a aplicação de técnicas de aproximação (remoção de camadas, contrações esparsas) dentro de um formalismo unificado.
• Limitações: O método mantém escala exponencial no pior caso. Questões de estabilidade numérica (subfluxo, perda de contraste em casos degenerados) e a necessidade de calibração dependente do tamanho são identificadas como limitações significativas.

Em resumo, o artigo fornece um formalismo rigoroso de rede de tensores para o TSP e suas variantes, demonstrando sua capacidade de recuperar soluções ótimas em instâncias pequenas e integrar restrições industriais, ao mesmo tempo em que reconhece que não supera a complexidade exponencial fundamental do problema.