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

Cet article présente une méthode de prétraitement pour le problème du voyageur de commerce qui réduit la taille du modèle en limitant les arcs candidats, améliorant ainsi les temps de calcul et les écarts d'optimalité sur des instances classiques et quantiques.

L'essentiel

🗺️ Le Problème du Vendeur de Journaux (et son Super-Plan)

Imaginez que vous êtes un vendeur de journaux dans une ville. Vous devez passer par chaque maison exactement une fois pour livrer les journaux, puis revenir à votre point de départ. Votre objectif ? Faire le plus court trajet possible pour économiser du temps et de l'essence.

C'est ce qu'on appelle le Problème du Voyageur de Commerce (ou TSP en anglais).

🤯 Le Problème : Trop de choix !

Le problème, c'est que le nombre de façons de faire ce tour est astronomique.

• Si vous avez 5 maisons, c'est gérable.
• Si vous avez 20 maisons, le nombre de combinaisons explose.
• Si vous avez 50 maisons, c'est comme essayer de trouver une aiguille dans une paille... qui serait elle-même faite de milliards d'aiguilles !

Les ordinateurs classiques (comme votre PC) et les nouveaux ordinateurs quantiques (les machines du futur) ont du mal à tout calculer car il y a trop de routes à vérifier. C'est comme si on vous demandait de goûter à tous les plats d'un restaurant pour trouver le meilleur, alors que le menu a 10 000 pages.

💡 La Solution : Le "Filtre Intelligent" (CAF)

Les auteurs de ce papier, Alessia, Luigi et Francesca, ont eu une idée géniale : avant même de commencer à chercher la solution parfaite, on va nettoyer le menu.

Ils ont créé une méthode appelée CAF (Cost-Based Arc Filtering). Voici comment ça marche avec une analogie simple :

Imaginez que vous êtes à une gare. Vous devez aller dans 100 villes différentes.

• Sans le filtre : Vous regardez tous les trains possibles, même ceux qui partent à l'autre bout du monde pour aller à une ville voisine. C'est du gaspillage !
• Avec le filtre (CAF) : Vous dites : "Pour chaque ville, je ne garde que les 50 trains les plus proches et les moins chers. Je jette tous les autres."

En mathématiques, ils utilisent un théorème célèbre (le théorème de Dirac) pour prouver une chose rassurante : même si on jette la moitié des routes, il reste toujours assez de chemins pour faire un tour complet sans se perdre. On ne perd pas la solution, on enlève juste le "bruit".

🧪 Les Résultats : Plus rapide, plus efficace

Les chercheurs ont testé cette méthode sur deux types d'ordinateurs :

1. Les ordinateurs classiques (comme le vôtre) :

   • Résultat : Le calcul est devenu beaucoup plus rapide. Pour des villes moyennes, le temps de calcul a été divisé par deux. C'est comme passer d'une voiture de ville à une Ferrari sur l'autoroute.

2. Les ordinateurs quantiques (les machines du futur) :

   • C'est là que c'est le plus excitant. Les ordinateurs quantiques actuels sont très fragiles et ne peuvent pas gérer de gros problèmes. Ils ont une "mémoire" limitée.
   • Grâce au filtre CAF, les chercheurs ont pu résoudre des problèmes avec 15 villes sur un ordinateur quantique.
   • Sans le filtre, c'était impossible. C'est comme si le filtre avait permis de faire passer un éléphant (le problème) à travers le trou d'une aiguille (l'ordinateur quantique) en le rendant plus petit et plus léger.

🎯 En résumé

Ce papier nous dit : "Ne cherchez pas l'aiguille dans toute la paille. D'abord, enlevez la paille inutile, puis cherchez l'aiguille dans ce qui reste."

• L'idée : Ne garder que les routes les plus courtes entre chaque ville.
• Le résultat : On résout le problème plus vite sur les ordinateurs d'aujourd'hui, et on arrive enfin à utiliser les ordinateurs quantiques pour des problèmes réels, pas juste des petits exercices théoriques.

C'est une étape importante pour rendre l'informatique quantique utile dans la vraie vie, que ce soit pour livrer des colis, organiser des tournées de bus ou planifier des circuits de livraison.

Résumé technique

1. Problématique

Le Problème du Voyageur de Commerce (TSP) est un problème d'optimisation combinatoire fondamental, classé comme NP-difficile. L'objectif est de trouver le chemin le plus court visitant chaque ville exactement une fois et revenant au point de départ.

• Défis : La complexité provient de la croissance exponentielle de l'espace de recherche et du grand nombre de contraintes nécessaires pour éliminer les sous-tours.
• Limites actuelles : L'application de techniques d'optimisation quantique (notamment le recuit quantique) au TSP est entravée par les limitations matérielles des processeurs quantiques actuels (nombre limité de qubits, connectivité restreinte). Les formulations classiques (QUBO ou CQM) deviennent rapidement ingérables pour des instances réalistes en raison du nombre élevé de variables de décision (arcs).

2. Méthodologie : Filtrage d'arcs basé sur le coût (CAF)

Les auteurs proposent une stratégie de prétraitement novatrice appelée Cost-Based Arc Filtering (CAF) visant à réduire la taille du modèle d'optimisation tout en garantissant la faisabilité du problème.

• Principe de base : Au lieu de considérer toutes les arêtes d'un graphe complet, la méthode ne conserve pour chaque sommet que les $k$ voisins les moins coûteux.
• Paramétrage théorique : Le nombre de voisins conservés est fixé à $k = \lceil n/2 \rceil$ (où $n$ est le nombre de villes).
• Justification théorique (Théorème de Dirac) :
  • Le théorème de Dirac en théorie des graphes stipule que si le degré minimum d'un graphe est $\ge n/2$, le graphe est hamiltonien (il contient un cycle passant par tous les sommets).
  • En conservant $k = \lceil n/2 \rceil$ arêtes par sommet, les auteurs garantissent mathématiquement que le sous-graphe résultant contient au moins un cycle hamiltonien, préservant ainsi la faisabilité du problème.
• Hypothèse d'optimalité : Pour les instances euclidiennes, les solutions optimales tendent à utiliser des arêtes courtes. Le filtrage élimine donc principalement les connexions à longue distance, concentrant l'espace de recherche dans la région la plus prometteuse.

3. Contributions Clés

1. Réduction de la complexité du modèle : La méthode CAF réduit drastiquement le nombre de variables de décision (arcs) sans sacrifier la possibilité de trouver une solution valide.
2. Évaluation hybride : L'approche est évaluée sur deux fronts :
   • Optimisation classique : Utilisation du solveur commercial Gurobi (Programmation Linéaire en Nombres Entiers - ILP).
   • Optimisation quantique : Utilisation du solveur hybride D-Wave LeapCQMHybrid (Constrained Quadratic Model) sur un processeur quantique Advantage2.
3. Benchmarking réaliste : Contrairement à de nombreuses études quantiques utilisant des problèmes artificiels, cette recherche utilise des instances réelles de la bibliothèque TSPLIB (notamment berlin52), offrant une évaluation plus rigoureuse.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances allant de 5 à 50 sommets (classique) et jusqu'à 15 sommets (quantique).

A. Impact sur la taille du modèle

• La méthode CAF réduit le nombre de variables de décision d'environ 30 % par rapport à la formulation complète.
• Cet écart s'élargit avec la taille de l'instance, rendant le modèle beaucoup plus compact et scalable.

B. Performance avec solveur classique (Gurobi)

• Qualité de la solution : Pour les instances jusqu'à $V=20$, la méthode préserve la solution optimale (écart d'optimalité de 0 %).
• Temps de calcul : CAF réduit significativement le temps de résolution. Pour des instances moyennes ($V \ge 10$), le temps de calcul diminue de 40 % à 54 %.
• Cas limites : Pour $V=21$, le solveur sans prétraitement atteint la limite de temps (300s) sans trouver de borne inférieure valide, tandis que la version avec CAF obtient une meilleure valeur d'objectif, démontrant son utilité même lorsque l'optimalité n'est pas prouvée.

C. Performance avec solveur quantique hybride (D-Wave)

• Faisabilité : Grâce à la réduction du nombre d'arcs, la méthode permet de résoudre des instances de TSP jusqu'à 15 clients avec une approche quantique, dépassant les limites habituelles de la littérature (souvent < 10).
• Qualité de la solution :
  • Pour les petites instances ($V \le 11$), les deux formulations atteignent l'optimum.
  • Pour les instances plus grandes ($V=13$), l'écart d'optimalité passe de 43 % (sans CAF) à 11 % (avec CAF).
  • Réduction moyenne de l'écart d'optimalité d'environ 29 % grâce au prétraitement.
• Efficacité temporelle : Le temps de résolution moyen diminue d'environ 5 % globalement, avec une réduction de 17 % pour la plus grande instance testée ($V=15$).

5. Signification et Conclusion

Cet article démontre que le prétraitement par filtrage d'arcs est une étape cruciale pour rendre l'optimisation du TSP viable sur les architectures quantiques actuelles.

• Scalabilité : La méthode améliore la scalabilité des formulations, permettant d'aborder des problèmes plus grands que ceux habituellement traités par les solveurs quantiques hybrides.
• Synergie Classique-Quantique : Bien que bénéfique pour les solveurs classiques, l'impact est encore plus critique pour l'optimisation quantique où la contrainte matérielle (nombre de qubits) est le goulot d'étranglement principal.
• Perspectives futures : Les auteurs suggèrent d'explorer des techniques de réduction de modèle alternatives et des procédures itératives pour affiner dynamiquement le modèle, visant à intégrer davantage les méthodes classiques et quantiques pour des problèmes à très grande échelle.

En résumé, le travail de Ciacco et al. propose une approche pragmatique et théoriquement fondée pour surmonter les limitations matérielles du calcul quantique dans le domaine du routage, tout en offrant des gains de performance immédiats pour les méthodes d'optimisation traditionnelles.