🤖 machine learning

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

Este artículo propone un enfoque de dos etapas para la esparsificación de grafos en el Problema del Viajante, que combina heurísticas clásicas para maximizar la cobertura y un modelo de aprendizaje automático para reducir la densidad, logrando así un rendimiento superior y generalizable en diversos tipos de distancias y escalas de problemas.

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

Publicado 2026-04-23

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que tienes que organizar una ruta de viaje para un repartidor que debe visitar 100 ciudades y regresar al punto de partida, gastando la menor cantidad de gasolina posible. Este es el famoso problema del "Viajante de Comercio".

El reto es que, si intentas calcular todas las rutas posibles entre todas las ciudades, el número de opciones es tan astronómico que ni la computadora más potente del mundo podría resolverlo en la vida de una persona. Es como intentar probar cada posible combinación de ingredientes en una receta gigante para ver cuál sabe mejor; tardarías siglos.

Para solucionar esto, los expertos usan un "atajo": en lugar de mirar todas las conexiones posibles, solo miran un subconjunto pequeño y prometedor de caminos. A esto se le llama "esparcimiento del grafo" (simplificar el mapa).

Aquí es donde entra el problema:

Si dejas demasiados caminos, la computadora sigue tardando mucho en buscar la mejor ruta.
Si dejas muy pocos caminos, corres el riesgo de cortar el camino perfecto y quedarte con una ruta mediocre.

Los métodos actuales son como dos tipos de expertos que dan consejos:

El experto "Vecino" (POPMUSIC): Es muy estricto y deja pocos caminos (el mapa es muy limpio), pero a veces se equivoca y borra el camino secreto que lleva a la solución perfecta, especialmente en ciudades muy grandes.
El experto "Cercano" (α-Nearest): Es más generoso y deja muchos caminos (el mapa es denso), asegurándose de no perder nada importante, pero la computadora se ahoga en tanta información.

La Solución Propuesta: El Método de "Dos Fases"

Los autores de este paper proponen una solución inteligente que combina lo mejor de ambos mundos usando Inteligencia Artificial (Machine Learning). Imagina que es como un proceso de filtrado en dos pasos:

Fase 1: La Red de Seguridad (La Unión)

Primero, toman los consejos de ambos expertos y los unen.

Analogía: Imagina que tienes dos guardias de seguridad revisando una lista de invitados. El guardia A dice "deja pasar a todos los que parecen amigos". El guardia B dice "deja pasar a todos los que parecen familiares".
En lugar de elegir a uno, pones a los dos a trabajar juntos. Si cualquiera de los dos dice "este camino es bueno", lo guardas en la lista.
Resultado: Tienes una lista de caminos casi perfecta (no te pierdes nada importante), pero la lista es muy larga y desordenada.

Fase 2: El Filtro Inteligente (La IA)

Aquí es donde entra la magia. Entrenan a una Inteligencia Artificial (un modelo de aprendizaje automático) para que actúe como un editor experto.

Analogía: Tienes esa lista larga y desordenada de la Fase 1. Le das la lista al editor (la IA) y le dices: "Quiero que cortes la mitad de esta lista, pero asegúrate de no borrar ningún camino que sea vital para el viaje perfecto".
¿Cómo sabe la IA qué cortar? La IA tiene un superpoder: sabe de dónde viene cada camino.
- Si un camino fue recomendado por ambos expertos (el guardia A y el B), la IA sabe: "¡Esto es oro! No lo toques".
- Si un camino fue recomendado solo por uno de ellos, la IA piensa: "Hmm, esto es sospechoso, probablemente sea un camino de relleno que puedo borrar".
La IA elimina los caminos "sospechosos" y deja solo los más fuertes.

¿Por qué es tan genial este método?

Funciona en cualquier terreno: A diferencia de otros métodos de IA que solo funcionan si las ciudades están en un mapa plano (como en un tablero de ajedrez), este método funciona incluso si las ciudades están en montañas, islas o en un mapa del mundo real con distancias extrañas. No necesita coordenadas, solo necesita saber qué tan lejos está un punto de otro.
Ahorra tiempo: Al limpiar la lista de caminos, el software que busca la ruta final (llamado LKH) puede trabajar mucho más rápido. En pruebas, el viaje se resolvió un 20% más rápido sin perder calidad.
Mejor cuanto más grande es el problema: Curiosamente, este método brilla más cuando el problema es gigante (500 ciudades). Los métodos antiguos fallaban al escalar, pero este método de "dos fases" se vuelve más inteligente y eficiente a medida que crece el tamaño del viaje.

En resumen

Imagina que quieres encontrar la mejor ruta para un viaje.

Paso 1: Pides a dos guías turísticos diferentes que te den sus mejores sugerencias y juntas todas sus ideas en una lista gigante para no perderte nada.
Paso 2: Contratas a un editor experto (la IA) que, sabiendo qué sugerencias fueron hechas por ambos guías, elimina rápidamente las sugerencias débiles y redundantes.

El resultado es un mapa optimizado: pequeño, rápido de leer, pero que contiene todas las rutas secretas necesarias para encontrar el viaje perfecto. Es una forma elegante de usar la inteligencia artificial para limpiar el ruido y dejar brillar la solución.

1. El Problema

Los solucionadores de alto rendimiento para el Problema del Viajante de Comercio (TSP), como LKH (Lin-Kernighan-Helsgaun), no exploran todas las posibles aristas entre ciudades. En su lugar, operan dentro de un grafo candidato esparsificado (un subconjunto pequeño de aristas).

El Dilema: La construcción de este grafo es crítica. Si se mantienen demasiadas aristas, el solucionador pierde tiempo de cómputo; si se eliminan demasiadas, se corre el riesgo de cortar aristas que pertenecen a la ruta óptima, degradando la calidad de la solución.
Limitaciones de los Métodos Actuales:
- Heurísticas clásicas: Los dos métodos líderes, $\alpha$ -Nearest y POPMUSIC, tienen compensaciones. POPMUSIC es muy esparso pero pierde recall (cobertura de la ruta óptima) en instancias grandes o distribuciones difíciles. $\alpha$ -Nearest es más estable pero genera grafos más densos.
- Métodos de Aprendizaje Automático (ML): Las aproximaciones existentes suelen operar sobre el grafo completo ( $N(N-1)/2$ aristas), lo cual es computacionalmente costoso y a menudo limitado a distancias euclidianas, ignorando otros tipos de métricas de distancia (como las definidas en TSPLIB).

2. Metodología Propuesta: Enfoque de Dos Etapas

Los autores proponen un pipeline de dos etapas que combina heurísticas clásicas con aprendizaje automático para maximizar la cobertura y luego reducir la densidad.

Etapa 1: Maximización del Recall (Unión Heurística)

En lugar de intentar aprender directamente sobre el grafo completo, la primera etapa construye un grafo base de alta cobertura mediante la unión de dos heurísticas:
$E_{union} = E_{\alpha\text{-Nearest}} \cup E_{\text{POPMUSIC}}$

Objetivo: Asegurar que casi todas las aristas de la ruta óptima estén presentes (cobertura casi perfecta, >99.9%).
Señal de Procedencia (Source Provenance): Esta unión crea una señal crítica: las aristas presentes en ambas heurísticas tienen una probabilidad extremadamente alta de ser parte de la ruta óptima, mientras que las que solo aparecen en una son candidatas a ser eliminadas.

Etapa 2: Poda Aprendida (Learned Pruning)

Sobre el grafo base denso de la Etapa 1, se entrena un modelo de ML para puntuar y eliminar aristas redundantes.

Características (Features): Se diseñaron 6 familias de características que dependen únicamente de los pesos de las aristas y la estructura del grafo candidato, no de las coordenadas geométricas. Esto hace que el método sea agnóstico al tipo de distancia (funciona para EUC_2D, ATT, MAN_2D, GEO).
- Incluyen: Rangos de distancia, normalización local, estructura de vecindad y, crucialmente, la procedencia de la fuente (¿está en $\alpha$ , en POP, o en ambos?).
Modelos: Se probaron Regresión Logística (LR), SVM Lineal y XGBoost.
Regla de Selección: En lugar de un umbral global, se utiliza una regla a nivel de nodo basada en una distribución softmax local para mantener un número mínimo de aristas por nodo (garantizando la factibilidad del tour) y controlar la densidad.

3. Contribuciones Clave

Pipeline de Dos Etagas Eficiente: Aplicar la poda aprendida a un grafo ya esparsificado (en lugar del grafo completo) reduce drásticamente la complejidad computacional y permite que modelos simples (como la regresión logística) funcionen excepcionalmente bien gracias a la señal de procedencia.
Señal de Procedencia como Guía: Demostraron que fusionar dos heurísticas crea una señal predictiva robusta. Esto permite que el modelo aprenda a distinguir aristas "seguras" (presentes en ambas heurísticas) de las redundantes, facilitando la generalización.
Generalización y Escalabilidad:
- Funciona en 4 tipos de distancia de TSPLIB y 5 distribuciones espaciales.
- Se entrena en instancias de tamaño $N=100$ y generaliza exitosamente a tamaños de $N=50$ hasta $N=500$ (5 veces el tamaño de entrenamiento).
- Supera a los métodos de poda neuronal recientes (como DIFUSCO, AttGCN) que están restringidos a distancias euclidianas y grafos completos.

4. Resultados Experimentales

Los experimentos se realizaron sobre 20 familias de instancias TSP (combinando 4 tipos de distancia y 5 distribuciones).

Reducción de Densidad: El método reduce la densidad del grafo candidato en un 37% - 47% en comparación con la unión base, manteniendo una cobertura de aristas óptimas $\ge$ 99.69% en todos los tamaños y tipos de distancia.
Rendimiento del Solucionador (LKH):
- Los grafos esparsificados permiten que LKH resuelva más rápido. La combinación Union + Regresión Logística logró una aceleración de 1.20x a 1.28x en tiempo de CPU sin aumentar la brecha de optimalidad (gap).
- En instancias grandes ( $N=500$ ), el método supera en cobertura a POPMUSIC puro, demostrando que la poda aprendida recupera la degradación que sufren las heurísticas individuales a gran escala.
Comparación con Métodos Neuronales:
- En instancias euclidianas ( $N=500$ ), el método propuesto logra mayor cobertura y menor densidad que DIFUSCO, AttGCN y DIMES.
- Ventaja de Hardware: El pipeline propuesto corre en CPU (tiempo de poda < 83 ms por instancia), mientras que los métodos neuronales requieren GPU y son más lentos en inferencia.
Robustez: El método mantiene un rendimiento estable en todos los tipos de distancia (EUC_2D, ATT, MAN_2D, GEO), a diferencia de los métodos basados en GNN que fallan en distancias no euclidianas.

5. Significado y Conclusiones

Cambio de Paradigma: El trabajo demuestra que no es necesario entrenar modelos sobre grafos completos para obtener buenos resultados en TSP. Operar sobre la unión de heurísticas fuertes es una estrategia superior.
Simplicidad vs. Complejidad: Se destaca que un modelo simple (Regresión Logística) es suficiente cuando se le proporciona la señal de procedencia correcta, evitando la necesidad de arquitecturas neuronales complejas y costosas.
Escalabilidad: El método resuelve el problema de degradación de las heurísticas en instancias grandes, ofreciendo una solución que mejora su valor a medida que aumenta la escala del problema.
Limitaciones: El estudio es empírico (sin garantías teóricas de preservación de optimalidad) y depende de la generación de rutas óptimas exactas (vía Concorde) para el entrenamiento, lo que limita su escalabilidad a instancias masivas ( $N > 1000$ ) donde calcular la óptima es inviable.

En resumen, este artículo presenta una solución práctica y altamente eficiente que combina lo mejor de la heurística clásica y el aprendizaje automático para optimizar la fase de pre-procesamiento en solucionadores de TSP, logrando mayor velocidad de resolución sin sacrificar la calidad de la solución.