Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

Resumen Técnico: Problema del Viajante de Comercio (TSP) con un Método de Preprocesamiento para Optimización Clásica y Cuántica

1. El Problema

El Problema del Viajante de Comercio (TSP) es un problema fundamental de optimización combinatoria que busca encontrar la ruta más corta que visite un conjunto de ciudades exactamente una vez y regrese al punto de origen.

• Desafío: Aunque su formulación es simple, el TSP es NP-duro. La complejidad crece exponencialmente con el número de ciudades debido al tamaño del espacio de búsqueda y la necesidad de un gran número de restricciones para eliminar subtours (ciclos desconectados).
• Limitaciones Actuales:
  • En la optimización clásica, los modelos de Programación Lineal Entera (ILP) se vuelven intratables para instancias grandes debido a la explosión de variables de decisión.
  • En la optimización cuántica (específicamente Quantum Annealing o Recocido Cuántico), las limitaciones de hardware (número de qubits, conectividad y requisitos de incrustación) impiden resolver instancias realistas. Los intentos anteriores han estado restringidos a problemas muy pequeños o artificialmente generados.

2. Metodología: Filtrado de Arcos Basado en Costos (CAF)

Los autores proponen una estrategia de preprocesamiento novedosa llamada CAF (Cost-Based Arc Filtering) para reducir el tamaño del modelo de optimización sin comprometer la factibilidad del problema.

• Principio Fundamental: En un grafo completo, el número de arcos es $O(n^2)$. La metodología se basa en la observación de que, en instancias euclidianas, las rutas óptimas tienden a utilizar arcos de menor costo (ciudades cercanas) y raramente incluyen conexiones de larga distancia.
• Algoritmo CAF:
  1. Para cada vértice $i$, se ordenan los arcos $(i, j)$ en orden creciente de costo $c_{ij}$.
  2. Se retienen solo los primeros $k$ vecinos, donde $k = \lceil n/2 \rceil$ (la mitad redondeada hacia arriba del número total de vértices).
  3. Se eliminan todos los demás arcos, reduciendo drásticamente el conjunto de variables de decisión.
• Garantía Teórica (Factibilidad):
  • El método se basa en el Teorema de Dirac de la teoría de grafos, que establece que un grafo con $n$ vértices es Hamiltoniano (contiene un ciclo que visita todos los vértices) si el grado mínimo de cada vértice es al menos $n/2$.
  • Al seleccionar $k = \lceil n/2 \rceil$ arcos por vértice, se garantiza matemáticamente que el grafo reducido resultante sigue siendo Hamiltoniano, preservando así la existencia de al menos una solución factible.

3. Contribuciones Clave

• Reducción de Modelos: Desarrollo de un método de preprocesamiento que reduce el número de variables de decisión en aproximadamente un 30% independientemente del tamaño de la instancia.
• Evaluación Híbrida: Análisis exhaustivo del TSP utilizando tanto solvers clásicos (Gurobi) como solvers cuánticos híbridos (D-Wave Leap CQM), una combinación poco común en la literatura actual.
• Escalabilidad Cuántica: Demostración de que es posible resolver instancias de TSP con hasta 15 clientes utilizando optimización cuántica, superando las limitaciones típicas de problemas "de juguete" o muy pequeños.
• Validación en Benchmarks Reales: Uso de instancias estándar de la librería TSPLIB (específicamente berlin52), en lugar de problemas sintéticos, proporcionando una evaluación más realista del potencial de la computación cuántica en problemas de enrutamiento.

4. Resultados Experimentales

Los experimentos se realizaron en instancias con un número de vértices ($V$) variable (de 5 a 21 para métodos clásicos y hasta 15 para cuánticos).

• Impacto en el Tamaño del Modelo:
  • La reducción de variables es consistente y aumenta con el tamaño del problema, pasando de un 10% de reducción en instancias pequeñas a un 36% en instancias más grandes.
• Optimización Clásica (Gurobi):
  • Calidad de Solución: El método CAF preserva la optimalidad; las soluciones óptimas encontradas son idénticas a las del modelo completo.
  • Tiempo de Cálculo: Se observa una reducción significativa en el tiempo de resolución. Para instancias medianas/grandes ($V \ge 10$), el tiempo de cálculo se reduce entre un 40% y un 54%. En promedio, la reducción es del 32%.
  • Escalabilidad: Para $V=21$, el modelo sin CAF no pudo encontrar una cota inferior válida en 300 segundos, mientras que el modelo con CAF encontró una solución viable con un valor objetivo mejor.
• Optimización Cuántica (D-Wave Hybrid):
  • Mejora en la Brecha de Optimalidad (Gap): El uso de CAF redujo la brecha de optimalidad promedio en un 31% (de un 16% a un 11% en el promedio de todas las instancias probadas).
  • Tasa de Éxito: Para instancias más grandes ($V=15$), el solver cuántico logró resolver el 40% de las ejecuciones, algo difícil de lograr sin el preprocesamiento debido a la complejidad del modelo.
  • Eficiencia: Se observó una reducción del tiempo de solución promedio de aproximadamente un 5-17% dependiendo del tamaño de la instancia.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

1. Puente entre Clásico y Cuántico: Demuestra que las técnicas de preprocesamiento clásicas son esenciales para habilitar el uso de hardware cuántico actual en problemas del mundo real.
2. Viabilidad Práctica: Al reducir el espacio de búsqueda, el método CAF hace que los modelos de TSP sean escalables para solvers híbridos, permitiendo abordar instancias que antes eran inalcanzables para la computación cuántica.
3. Dirección Futura: Establece una base para el desarrollo de procedimientos iterativos y técnicas de reducción de modelos dinámicas que podrían integrarse en flujos de trabajo de optimización híbrida más avanzados, maximizando el potencial de la computación cuántica a medida que el hardware evoluciona.

En conclusión, el artículo valida que el filtrado de arcos basado en costos no solo es una heurística eficiente para solvers clásicos, sino un requisito habilitador para aplicar con éxito la optimización cuántica a problemas de enrutamiento logístico realistas.