🤖 machine learning

Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

Este artigo propõe uma abordagem de esparsificação de grafos em duas etapas para o Problema do Caixeiro Viajante, que combina heurísticas clássicas para maximizar a cobertura e um modelo de aprendizado de máquina para reduzir a densidade, superando métodos existentes ao generalizar eficazmente para diferentes tipos de distâncias e distribuições espaciais em diversas escalas de problemas.

Autores originais: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

Publicado 2026-04-23

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você precisa organizar uma viagem de negócios para visitar 500 cidades diferentes, começando e terminando na mesma cidade, gastando o mínimo de combustível possível. Este é o famoso Problema do Caixeiro Viajante.

O desafio é que, com 500 cidades, existem trilhões de trilhões de rotas possíveis. Tentar calcular todas elas seria como tentar encontrar uma agulha em um palheiro que é do tamanho de um planeta. Os computadores ficariam loucos antes de encontrar a resposta.

Para resolver isso, os computadores usam "atalhos". Eles não olham para todas as estradas possíveis, mas sim para um mapa reduzido (uma lista de apenas algumas estradas promissoras) e tentam encontrar o melhor caminho apenas dentro desse mapa.

O problema é: como criar esse mapa reduzido sem cortar a estrada que leva à solução perfeita?

Se você cortar muitas estradas, pode acabar sem a rota ideal (o computador fica "cego").
Se deixar muitas estradas, o computador demora muito para decidir (o computador fica "lento").

Os autores deste artigo propuseram uma solução inteligente em duas etapas, como se fosse uma equipe de detetives trabalhando juntos.

A Metáfora: O Detetive Velho e o Detetive Jovem

Imagine que você tem dois especialistas em rotas:

O Detetive "Cuidadoso" (POPMUSIC): Ele é muito esperto em encontrar caminhos curtos e eficientes, mas quando a cidade fica gigante, ele começa a esquecer algumas estradas importantes.
O Detetive "Seguro" (α-Nearest): Ele é um pouco mais conservador. Ele não deixa de colocar quase nenhuma estrada no mapa. O mapa dele é grande, mas é muito difícil ele errar e cortar uma estrada essencial.

O Problema:

Usar só o "Cuidadoso" é arriscado em cidades grandes (ele esquece coisas).
Usar só o "Seguro" é lento (o mapa é gigante demais).
Usar os dois juntos (juntar os mapas) garante que nenhuma estrada importante seja perdida, mas o mapa fica enorme e cheio de "lixo" (estradas que ninguém vai usar).

A Solução: A Abordagem em Duas Etapas

Os autores criaram um método novo que funciona assim:

Etapa 1: A "Rede de Segurança" (Maximizar a Cobertura)

Em vez de escolher um dos detetives, eles pegam os dois mapas e colam um em cima do outro.

Resultado: Eles têm um mapa gigante, mas com a garantia de que quase 100% das estradas importantes estão lá. Nada foi perdido. É como ter uma rede de pesca com malhas tão finas que nenhum peixe escapa.

Etapa 2: O "Filtro Inteligente" (Reduzir o Tamanho)

Agora, eles usam um Inteligência Artificial (IA) simples para olhar esse mapa gigante e dizer: "Ok, temos muitas estradas aqui. Vamos ver quais são realmente necessárias?".

Aqui está o "pulo do gato" (a parte genial):
A IA não precisa adivinhar do zero. Ela usa um pista de confiança:

Se uma estrada aparece nos mapas dos dois detetives, a IA sabe que ela é muito importante (provavelmente faz parte da rota perfeita).
Se uma estrada aparece no mapa de apenas um dos detetives, ela é suspeita e pode ser cortada.

A IA aprende a identificar esses padrões e remove as estradas "suspeitas" (as que só um dos detetives sugeriu), deixando o mapa pequeno e rápido, mas mantendo as estradas seguras.

Por que isso é incrível?

Funciona em qualquer lugar: A maioria dos métodos modernos só funciona bem em mapas "retos" (como em uma cidade planejada). Este método funciona em qualquer tipo de terreno (montanhas, ilhas, distâncias estranhas), porque ele não olha para coordenadas geográficas, mas sim para a "lógica" das distâncias.
É mais rápido: Ao remover cerca de 40% a 47% das estradas desnecessárias, o computador resolve o problema muito mais rápido, sem perder a qualidade da solução.
Escalável: Funciona bem tanto para 50 cidades quanto para 500. Na verdade, quanto maior a cidade, mais útil esse método se torna, porque os métodos antigos começam a falhar em tamanhos grandes.

Resumo da Ópera

Pense nisso como organizar uma festa gigante:

Método Antigo: Você convida todo mundo que você conhece (muita gente, festa lenta) ou convida só os seus melhores amigos (pouca gente, mas pode faltar alguém importante).
Método Novo: Você faz uma lista com todos os seus conhecidos (garantindo que ninguém importante fique de fora) e depois pede para um amigo muito observador (a IA) dizer quem realmente vai gostar da festa e quem pode ficar de fora. O resultado é uma lista de convidados perfeita: nem muito grande, nem muito pequena, e ninguém importante foi esquecido.

Os autores mostraram que essa técnica é tão boa que supera até métodos complexos de "Deep Learning" (redes neurais profundas) que exigem computadores superpotentes, e ainda funciona em computadores comuns, de forma rápida e eficiente.

Resumo Técnico: Esparsificação de Grafos em Duas Etapas para o Problema do Caixeiro Viajante (TSP)

1. O Problema

Os solucionadores de alta performance para o Problema do Caixeiro Viajante (TSP), como o LKH (Lin-Kernighan-Helsgaun), não exploram todas as arestas possíveis entre $N$ cidades. Em vez disso, operam dentro de um grafo candidato esparsificado (um subconjunto de arestas).

O Dilema: A esparsificação é um equilíbrio delicado. Manter muitas arestas desperdiça tempo de computação; remover muitas pode eliminar arestas essenciais para a solução ótima, degradando a qualidade da rota.
Limitações Atuais: Os dois métodos heurísticos líderes, $\alpha$ -Nearest e POPMUSIC, são eficazes, mas nenhum é ideal para todos os cenários:
- POPMUSIC: Gera grafos muito esparsos, mas sua capacidade de recuperar arestas da solução ótima (recall) degrada-se em instâncias grandes ou distribuições difíceis.
- $\alpha$ -Nearest: É mais estável, mas gera grafos mais densos.
- União: A união dos dois maximiza o recall, mas resulta em densidade excessiva.
Limitação do Aprendizado de Máquina (ML): Métodos existentes de ML para esparsificação geralmente operam no grafo completo ( $N(N-1)/2$ arestas), o que é computacionalmente caro e frequentemente restrito a distâncias Euclidianas, falhando em outros tipos de métricas do TSPLIB.

2. Metodologia Proposta

Os autores propõem uma abordagem de duas etapas que aplica aprendizado de máquina sobre um grafo já esparsificado, em vez do grafo completo.

Etapa 1: Maximização do Recall (Construção da Base)
- O grafo candidato base ( $G_b$ ) é construído pela união das arestas selecionadas pelo $\alpha$ -Nearest e pelo POPMUSIC.
- Objetivo: Garantir uma cobertura quase perfeita das arestas da solução ótima.
- Sinal de Proveniência: Esta união cria um sinal crucial: uma aresta pode vir de apenas um heurístico ou de ambos. A presença em ambos é um forte indicador de que a aresta pertence à solução ótima.
Etapa 2: Poda Aprendida (Redução de Densidade)
- Um modelo de ML é treinado para pontuar cada aresta no grafo base ( $G_b$ ) e remover as de menor pontuação.
- Características (Features): O modelo utiliza vetores de características baseados apenas em pesos de arestas e estatísticas locais (ranks, razões, z-scores), tornando-o agnostico ao tipo de distância (funciona para Euclidiano, Manhattan, GEO, ATT, etc.).
- Modelos Testados: Regressão Logística (LR), SVM Linear e XGBoost.
- Regra de Seleção: Em vez de um limiar global, usa-se uma regra por nó baseada em uma distribuição softmax local, mantendo um número mínimo de arestas por nó para garantir a viabilidade da rota.

3. Contribuições Principais

Pipeline de Duas Etapas Eficiente: A aplicação de poda aprendida sobre grafos já esparsificados (e não no grafo completo) permite reduzir a densidade em até 47% mantendo $\ge 99,69\%$ das arestas da solução ótima.
Sinal de Proveniência como Facilitador: A fusão de dois heurísticos cria um sinal de "proveniência" (origem da aresta) que torna o problema de aprendizado trivial. Mesmo modelos simples, como Regressão Logística, funcionam bem, pois a presença em ambos os heurísticos é um indicador robusto de importância.
Generalização e Escalabilidade:
- O método generaliza para 4 tipos de distância e 5 distribuições espaciais diferentes.
- Demonstra-se que a abordagem torna-se mais valiosa em escalas maiores: a partir de $N=200$ , a abordagem combinada supera o POPMUSIC (que é o melhor heurístico único em escalas pequenas) em termos de cobertura.
- O modelo treinado em $N=100$ transfere-se estável para instâncias 5 vezes maiores ( $N=500$ ).

4. Resultados Experimentais

Os experimentos foram realizados em 20 famílias de instâncias TSP (variação de 4 tipos de distância $\times$ 5 distribuições espaciais), com tamanhos de $N=50$ a $N=500$ .

Redução de Densidade: O método (especialmente com XGBoost) reduziu o número de arestas de ~6N (na base de união) para ~3,14N em instâncias de $N=500$ , mantendo alta cobertura.
Desempenho do Solucionador (LKH):
- A poda resultou em acelerações consistentes de 1,20x a 1,28x no tempo de resolução do LKH.
- Qualidade da Solução: O gap de otimalidade não aumentou; em muitos casos, diminuiu ligeiramente, indicando que as arestas removidas eram redundantes para a qualidade da rota.
Comparação com Métodos Neurais:
- Em instâncias Euclidianas ( $N=500$ ), o método proposto superou abordagens neurais recentes (DIFUSCO, AttGCN, DIMES) em cobertura (atingindo >99% vs. quedas para <97% em distribuições difíceis) e operou com menor densidade.
- Diferente dos métodos neurais, que exigem GPUs e são restritos a coordenadas Euclidianas, a abordagem proposta roda em CPU e funciona em qualquer métrica de distância.
Caso Difícil (Corredor): A única limitação observada foi em instâncias do tipo "Corridor" (distribuição linear com arestas longas), onde a cobertura caiu para ~98,9% em $N=500$ , mas ainda assim superou os heurísticos individuais.

5. Significado e Conclusão

Este trabalho demonstra que a combinação de heurísticas clássicas robustas com aprendizado de máquina leve (aplicado em um espaço de busca já reduzido) é superior a tentar aprender a esparsificação do zero no grafo completo.

Inovação: A criação de um sinal de proveniência via união de heurísticos transforma um problema de aprendizado difícil (desbalanceado e de alta dimensão) em um problema fácil e robusto.
Impacto Prático: Oferece uma solução pronta para uso que acelera solucionadores TSP de ponta sem sacrificar a qualidade da solução, sendo aplicável a diversos tipos de problemas logísticos e de roteamento que não são estritamente Euclidianos.
Limitações: O método é empírico (sem garantias teóricas de preservação de todas as arestas ótimas) e depende de soluções exatas (via Concorde) para o treinamento, o que limita a escalabilidade para tamanhos de instância extremamente grandes durante a fase de treino.

Em suma, a abordagem de "duas etapas" (União Heurística + Poda Aprendida) estabelece um novo estado da arte para a pré-processamento de grafos em problemas de otimização combinatória, equilibrando eficiência computacional e robustez estatística.