Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Este artículo presenta una formulación basada en redes de tensores para el Problema del Viajante de Comercio y sus variantes que utiliza capas ponderadas por Boltzmann y filtros de conteo para identificar rutas ópticas mediante una regla marginal secuencial, sirviendo como una heurística para aplicaciones industriales a pequeña escala en lugar de una alternativa superior a los solucionadores clásicos especializados.

Lo esencial

El Panorama General: Resolver el Puzzle del "Viajante de Comercio" con un Nuevo Tipo de Calculadora

Imagina que eres un viajante de comercio. Tienes un mapa con 10, 20 o incluso 100 ciudades. Necesitas visitar cada ciudad exactamente una vez y regresar a casa, pero quieres hacerlo en la distancia más corta posible para ahorrar gasolina y tiempo. Este es el famoso Problema del Viajante de Comercio (TSP).

El problema es que, a medida que añades más ciudades, el número de rutas posibles explota. Es como intentar encontrar la llave perfecta en un montón de llaves que crece tan rápido que revisar cada una tomaría más tiempo que la edad del universo. Por eso las computadoras tienen dificultades con esto.

Este artículo introduce una nueva forma de abordar este problema utilizando Redes de Tensores. Piensa en una Red de Tensores no como un programa informático, sino como un sistema gigante de filtros multicapa.

La Analogía: El Tamiz de "Polvo de Oro"

Imagina que tienes una bolsa gigante de arena mezclada con polvo de oro.

• La Arena: Representa todas las rutas malas, largas e ineficientes.
• El Oro: Representa la ruta perfecta y más corta.
• El Objetivo: Quieres separar el oro de la arena sin mirar cada grano individualmente.

Los autores construyeron una máquina (la Red de Tensores) para hacer esto:

1. La Mezcla Inicial (La Superposición): Primero, la máquina crea una "superposición". Imagina que mágicamente crea una copia de cada ruta posible al mismo tiempo. Es como tener un millón de versiones diferentes de ti mismo, cada una tomando un camino distinto.
2. La Ponderación (El Calor): A continuación, la máquina aplica una "temperatura" (llamada $\tau$). Piensa en esto como una lámpara de calor.
   • Las rutas largas e ineficientes (la arena) se calientan y se convierten en luz, desvaneciéndose.
   • Las rutas cortas y eficientes (el oro) se mantienen frescas y pesadas.
   • La máquina utiliza matemáticas (factores de Boltzmann) para hacer que las rutas malas desaparezcan más rápido que las buenas.
3. Los Filtros (Las Reglas): Esta es la parte más importante. No puedes tener cualquier ruta; no puedes visitar la misma ciudad dos veces. Los autores construyeron Filtros de Conteo especiales.
   • Imagina un guardia de seguridad en cada ciudad. Si un viajero intenta visitar una ciudad a la que ya ha ido, el guardia cierra de golpe la puerta de esa ruta específica.
   • Estos filtros son "dispersos", lo que significa que son muy eficientes bloqueando los caminos incorrectos sin necesidad de revisar manualmente cada posibilidad individual.
4. El Resultado (La Marginal): Después de pasar por el calor y los filtros, la máquina comprime todo. Pregunta: "Si miro la primera ciudad, ¿cuál es la más probable de ser parte de la ruta ganadora?". Elige esa, la fija, y luego repite el proceso para la segunda ciudad, y así sucesivamente, hasta que se construye toda la ruta.

Lo Que Realmente Hicieron (Los Experimentos)

Los autores no afirmaron que este método sea una bala mágica que resuelva cada problema instantáneamente. Fueron muy honestos sobre sus limitaciones.

• Pruebas Pequeñas: Probaron su método en mapas pequeños (de 5 a 12 ciudades).
• Calibración: Descubrieron que la configuración de "temperatura" ($\tau$) es crucial. Si es demasiado baja, las rutas malas no se desvanecen lo suficiente. Si es demasiado alta, la computadora se confunde por pequeños errores matemáticos. Tuvieron que ajustar cuidadosamente esta configuración para cada tamaño de mapa.
• Los Resultados:
  • Cuando ajustaron los parámetros perfectamente, su método encontró la ruta perfecta aproximadamente el 95% de las veces en estos mapas pequeños.
  • Cuando lo compararon con métodos informáticos estándar (como "Codicioso" o "Recocido Simulado"), su método a menudo fue mejor para encontrar la ruta perfecta.
  • Sin embargo, admitieron que para mapas muy grandes, las matemáticas siguen volviéndose demasiado pesadas (complejidad exponencial), al igual que los métodos antiguos. No es un milagro de "tiempo polinomial"; es simplemente una forma diferente y muy estructurada de hacer las matemáticas.

Prueba en el Mundo Real: El Problema de Reasignación de Trabajos

Para ver si esto funciona fuera de la teoría, lo aplicaron a un problema industrial real para ONCE (una organización española para personas ciegas).

• El Problema: Tenían trabajadores asignados a trabajos y algunos trabajos vacíos. Necesitaban ver si mover a un trabajador a un nuevo trabajo haría que todo el equipo fuera más productivo.
• El Giro: Esto no es exactamente un problema de "viaje", pero es similar: tienes que asignar trabajos únicos a personas únicas sin hacer doble reserva.
• El Resultado: Compararon su método de Red de Tensores con otras dos herramientas poderosas (un recocido cuántico y un recocido digital).
  • Los resultados fueron idénticos en términos de ganancia total de productividad.
  • Las únicas diferencias ocurrieron en situaciones de "empate" donde dos opciones eran matemáticamente iguales; las máquinas simplemente eligieron diferentes opciones al azar.
  • Conclusión: Esto demostró que su método funciona en el mundo real y puede integrarse en software industrial, incluso si no supera a las herramientas especializadas en esta tarea específica.

La Conclusión

El artículo presenta un nuevo kit de herramientas matemáticas para resolver puzzles de enrutamiento y asignación.

• Lo Bueno: Ofrece una manera muy clara y modular de manejar reglas complejas (como "no visitar la misma ciudad dos veces") y puede encontrar soluciones perfectas en problemas pequeños. Es como tener un asistente altamente organizado y que sigue las reglas, que nunca se cansa de verificar las restricciones.
• Lo Malo: No hace mágicamente que los problemas grandes sean fáciles. Las matemáticas siguen volviéndose exponencialmente más difíciles a medida que crece el problema. Requiere un ajuste cuidadoso (calibración) para funcionar bien.
• La Lección: Es una nueva y poderosa forma de pensar sobre estos problemas y una herramienta sólida para tareas industriales específicas y de menor escala, pero aún no es un reemplazo para todos los solucionadores súper rápidos existentes.

En resumen: Construyeron un tamiz sofisticado que puede filtrar las rutas malas y encontrar la mejor, pero aún tienes que alimentarlo con la configuración correcta para obtener el oro.

Resumen técnico

Resumen Técnico: Formulación de Red Tensorial del Problema del Viajante de Comercio y Variantes

Definición del Problema
El artículo aborda el Problema del Viajante de Comercio (TSP) y varias de sus generalizaciones, incluyendo el TSP dependiente del tiempo (TDTSP), el Problema de Reasignación de Trabajos (JRP) y variantes que involucran restricciones de no repetición, reglas de precedencia, restricciones de grupo y objetivos de cuello de botella. El TSP se define como encontrar la ruta más corta que visite $N$ nodos exactamente una vez y regrese al inicio, un problema conocido como NP-duro. Si bien existen algoritmos exactos como Held-Karp ($O(N^2 2^N)$) y ramificación y poda, enfrentan una complejidad exponencial que limita su escalabilidad para casos industriales. Por el contrario, las heurísticas (por ejemplo, algoritmos genéticos, búsqueda local) ofrecen soluciones aproximadas sin garantías de optimalidad. Los autores señalan que los algoritmos cuánticos emergentes (QAOA, VQE) están actualmente limitados por el ruido del hardware (era NISQ), lo que motiva la exploración de técnicas clásicas que imitan las propiedades de los sistemas cuánticos.

Metodología
La contribución central es una formulación de red tensorial (TN) que representa los recorridos candidatos como estados en un espacio de producto tensorial. El método opera a través de tres mecanismos principales:

1. Construcción de la Red Tensorial:

   • Inicialización ('+'): Crea una superposición uniforme de todas las asignaciones de nodos posibles para cada paso de tiempo.
   • Optimización ('S'): Aplica un operador de evolución en tiempo imaginario $U = e^{-\tau C(\vec{y})}$, donde $\tau$ es un factor de amortiguamiento y $C(\vec{y})$ es el costo del recorrido. Esto suprime exponencialmente las configuraciones de alto costo, análogo a encontrar el estado fundamental en sistemas cuánticos.
   • Filtrado de Restricciones ('F'): Introduce capas de Operador de Producto Matricial (MPO) para hacer cumplir las restricciones. Para el TSP estándar, estas capas actúan como filtros de conteo que aseguran que cada nodo aparezca exactamente una vez. Los filtros utilizan índices de enlace binarios para rastrear si un nodo específico ha sido visitado, implementando efectivamente la restricción del símbolo de Levi-Civita $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$.
   • Extracción ('+'): Una capa de traza suma las amplitudes para producir pesos marginales.

2. Extracción Secuencial de Marginales:
   La solución se extrae iterativamente. Para un prefijo fijo del recorrido, el algoritmo calcula el peso marginal $Z_p(a; \tau)$ para cada nodo candidato $a$ en la siguiente posición. En el límite de $\tau \to \infty$ y aritmética exacta, el nodo que maximiza este peso está garantizado para ser parte de un recorrido óptimo (Proposición 3.2). El algoritmo selecciona el nodo maximizador, actualiza el prefijo y repite hasta completar el recorrido.

3. Generalizaciones:
   El marco se adapta para varias variantes del TSP modificando las capas de filtro y evolución:

   • DNSNN (Número Diferente de Pasos/Nodos): Los filtros permiten que los nodos aparezcan entre $N^0$ y $N^f$ veces.
   • NMTSP (No Markoviano): Utiliza MPOs de orden superior para manejar costos dependientes de los $K$ pasos anteriores.
   • BTSP (Cuello de Botella): Reemplaza la evolución de costos con una capa que rastrea el costo de arista máximo encontrado.
   • PTSP (Restringido por Grupos): Los filtros hacen cumplir la visita de exactamente un nodo por clase.
   • TSPP (Precedencia): Los proyectores locales suprimen nodos si sus predecesores requeridos aún no han aparecido.
   • JRP (Reasignación de Trabajos): Modelado como un problema de asignación lineal donde un estado de "sin movimiento" es repetible, y las vacantes específicas son únicas.

4. Aproximación y Complejidad:
   La contracción exacta de la red tensorial completa es exponencial, escalando como $O(\hat{N}^4 2^{\hat{N}})$ para una contracción densa por capas. Para abordar instancias más grandes, los autores proponen:

   • Ablación de Capas: Aplicar solo un subconjunto de capas de restricción para reducir la complejidad, tratando el resultado como una heurística.
   • Contracción Local Esparsa: Explotar la naturaleza determinista y dispersa de los tensores de filtro locales para reducir los prefactores polinómicos (por ejemplo, de $O(\hat{N}^4 2^{\hat{N}})$ a $O(\hat{N}^3 2^{\hat{N}})$) sin cambiar la escala exponencial.
   • Heurística de $\tau$ Finito: Usar precisión finita y $\tau$ finito para aproximar el límite de temperatura cero, reconociendo que el contraste numérico y las degeneraciones afectan la calidad de la solución.

Contribuciones Clave

• Fórmula Marginal Explícita: Derivación de una ecuación marginal de red tensorial cuyo límite de aritmética exacta y temperatura cero identifica un recorrido factible óptimo mediante una regla marginal secuencial.
• Codificación de Restricciones: Definición de capas MPO para restricciones de conteo (no repetición) aplicables a diversos problemas combinatorios.
• Marco de Generalización: Una construcción modular que adapta el formalismo TN a variantes del TSP (TDTSP, JRP, BTSP, etc.) alterando capas tensoriales específicas.
• Implementación Heurística: Una implementación de precisión finita y $\tau$ finito que funciona como una heurística calibrada, con un análisis de su comportamiento respecto al contraste numérico y la degeneración.

Resultados
El estudio experimental se centra en instancias sintéticas pequeñas ($N \in \{5, \dots, 12\}$) para validar la corrección del método y su comportamiento numérico, en lugar de reclamar superioridad computacional sobre solucionadores especializados.

• Calibración: El parámetro de tiempo imaginario $\tau$ depende del tamaño. Un barrido de calibración ($\tau \in \{1, \dots, 40\}$) mejoró significativamente la tasa de solución óptima del 55.56% (en $\tau=1$) al 95.56% en el conjunto de evaluación.
• Comparación de Solucionadores: En instancias pequeñas, el solucionador TN calibrado logró una tasa de optimalidad del 95.24%, superando a la codicia de NetworkX (26.67%) y al recocido simulado (59.05%), pero quedando por debajo de la referencia exacta de Held-Karp (100%).
• Ablación de Capas: Eliminar capas de restricción degradó la calidad de la solución, confirmando que el conjunto completo de filtros es necesario para una alta precisión.
• Caso Industrial (JRP): En una prueba de concepto para el Problema de Reasignación de Trabajos de ONCE, el método TN produjo soluciones con costos acumulados idénticos al Annealer Digital de Azure, diferenciándose solo en casos degenerados donde existen múltiples asignaciones óptimas.

Significado y Reclamaciones
Los autores declaran explícitamente modestia respecto al poder computacional del método. No reclaman una ventaja computacional general sobre solucionadores clásicos especializados (como Held-Karp, ramificación y corte, o algoritmos específicos de asignación) para el TSP general.

• Representación Formal: El trabajo se presenta como una "representación formal de tiempo exponencial de aritmética exacta" y una "plataforma para aproximaciones y extensiones controladas".
• Naturaleza Heurística: La implementación de $\tau$ finito se caracteriza como una "heurística calibrada de precisión finita" cuyo comportamiento depende del contraste numérico y las degeneraciones.
• Utilidad: El valor principal reside en el marco modular de red tensorial, que permite la integración sistemática de diversas restricciones (precedencia, grupos, costos no markovianos) y la aplicación de técnicas de aproximación (eliminación de capas, contracciones dispersas) dentro de un formalismo unificado.
• Limitaciones: El método conserva la escala exponencial en el peor de los casos. Se identifican problemas de estabilidad numérica (desbordamiento inferior, pérdida de contraste en casos degenerados) y la necesidad de calibración dependiente del tamaño como limitaciones significativas.

En resumen, el artículo proporciona un formalismo riguroso de red tensorial para el TSP y sus variantes, demostrando su capacidad para recuperar soluciones óptimas en instancias pequeñas e integrar restricciones industriales, mientras reconoce que no supera la complejidad exponencial fundamental del problema.