Resumen Técnico: Relajación Analítica de Tiempo Polinómico del Problema del Viajante (TSP)

Planteamiento del Problema

El Problema del Viajante (TSP) se identifica como un desafío de optimización combinatoria canónico de tipo NP-duro. Las soluciones exactas tradicionales, tales como la Programación Lineal Entera (ILP) y el algoritmo de programación dinámica de Held-Karp, requieren la evaluación del espacio de ciclos hamiltonianos de un grafo ponderado. Estos métodos están limitados por complejidades computacionales factoriales $O(N!)$ o exponenciales $O(N^2 2^N)$, lo que los hace impracticables para aplicaciones del mundo real que involucran instancias de problema mayores a aproximadamente $N \le 25$.

Metodología

El artículo propone un nuevo marco analítico continuo que mapea espacios de permutaciones discretas sobre un colector de tensores de flujo de probabilidad continuo. En lugar de recorrer árboles de búsqueda discretos, el método reformula la tarea de optimización como un problema algebraico de propagación de tensores. El enfoque está gobernado por tres postulados centrales:

1. Incrustación en un Colector Continuo: Las permutaciones discretas se incrustan en un espacio de tensores de flujo de probabilidad continuo $P \in \mathbb{R}^{N \times N}$. Las probabilidades de transición se definen mediante leyes de potencia de costos inversos, donde la probabilidad $P_{ij}$ es inversamente proporcional a los gradientes de peso de las aristas elevado a un parámetro de escala $\alpha$.
2. Normalización Transcendental y Acumulativa Dependiente de la Historia: Para imponer las restricciones hamiltonianas sin el enmascaramiento exponencial de subconjuntos, las probabilidades de las rutas se ponderan dinámicamente. El artículo introduce tres formulaciones analíticas:
   • Enfoque 1 (Flujo de Probabilidad Estándar): Califica las transiciones basándose en la relación entre la probabilidad y el costo de la arista.
   • Enfoque 2 (Heurística Pi-Exponencial): Aplica una escala trascendental utilizando $\pi$ a los valores de probabilidad.
   • Enfoque 3 (Relajación HK Trascendental): Utiliza un factor de matriz estático precalculado $\gamma(N) = \pi^{(N^2 / 2^N)}$.
3. Truncamiento de la Serie Espectral: El permanente intratable de las coberturas de ciclos se aproxima mediante expansiones de series de Maclaurin truncadas de la función generatriz exponencial de la matriz exponencial $e^{tW}$. Esto reduce la extracción de coeficientes a límites de multiplicación de matrices polinómicas, específicamente $O(N)$.

El algoritmo resultante opera en tres fases: Inicialización del Tensor, Construcción del Tensor de Transición y Propagación de Estado Secuencial. Ejecuta $N$ pasos para evaluar los nodos no visitados, seleccionando el puntaje mínimo de costo-a-probabilidad, logrando un tiempo de ejecución determinista estricto de $O(N^3)$.

Contribuciones Clave

• Cambio Algorítmico: Un algoritmo determinista que evita la enumeración exponencial de subconjuntos mediante el uso de matrices estocásticas, factores de escala trascendentales y series de Maclaurin truncadas.
• Reducción de Complejidad: Reducción teórica de la generación de la ruta TSP de un tiempo exponencial a un tiempo polinómico estricto de $O(N^3)$.
• Implementación: Provisión de implementaciones de código tanto en Python (NumPy) como en Java, demostrando la viabilidad del enfoque de propagación de tensores.
• Escalabilidad: Demostración de una escalabilidad estable para topologías de grafos de escala empresarial, con tiempos de ejecución que permanecen bajos incluso cuando $N$ aumenta.

Resultados

El artículo presenta resultados de pruebas comparativas exhaustivas para tamaños de problema desde $N = 1$ hasta $100$, comparando los enfoques analíticos propuestos contra las líneas base exactas de Held-Karp.

• Tiempo de Ejecución: El método propuesto de $O(N^3)$ demuestra tiempos de ejecución significativamente más rápidos en comparación con Held-Karp. Para $N=20$, el método propuesto toma 0.205 ms, mientras que Held-Karp requiere 870,000 ms. Para $N=100$, el método propuesto se completa en 15.80 ms, mientras que se señala que Held-Karp requiere búsquedas de "Arreglo Estático" (implicando que el método exponencial es inviable).
• Calidad de la Solución: Se informa que los costos de las rutas generados por los enfoques propuestos se alinean empíricamente con las líneas base óptimas conocidas.
  • Enfoque 1 y Enfoque 3: Estos métodos producen costos idénticos a la línea base exacta de Held-Karp en todas las instancias probadas ($N=1$ a $100$).
  • Enfoque 2: Este método muestra desviaciones menores (por ejemplo, en $N=6$, el costo es 399.10 frente a 398.50 del exacto), pero permanece cerca de la línea base óptima.
• Escalabilidad a Gran Escala: El artículo incluye proyecciones para grafos ultra grandes de hasta $N = 10,000$. Estima que para $N = 10,000$, el algoritmo requeriría aproximadamente $1.00 \times 10^{12}$ FLOPs, 800 MB de memoria y un tiempo de ejecución de aproximadamente 15.80 minutos.

Significado y Reivindicaciones

El artículo afirma que, al reencuadrar la optimización combinatoria a través de tensores algebraicos continuos, escalas trascendentales y aproximaciones de series polinómicas, la generación de rutas TSP puede ejecutarse de manera determinista en tiempo polinómico. El autor sostiene que este marco permite evitar la enumeración exponencial de subconjuntos manteniendo la alineación empírica con las soluciones óptimas.

El significado de este trabajo se presenta como una solución potencial a las limitaciones de escalabilidad de los solvers actuales de TSP, permitiendo el manejo de topologías de grafos de escala empresarial que anteriormente estaban restringidas a instancias pequeñas. El artículo concluye señalando que el trabajo futuro explorará la aceleración de hardware mediante núcleos de tensores de GPU para optimizar aún más el rendimiento para instancias de grafos dispersos masivos ($N > 10,000$).