Accelerating TSP Solving by Using Cost-Based Solution Densities of Relaxations

RÉSUMÉ : Le problème du voyageur de commerce, ou problème du commis voyageur, est l'un des problèmes les plus importants dans le domaine de l'optimisation combinatoire. Il a fait l'objet d'innombrables travaux de recherche, à la fois théoriques et pratiques. Parmi les aspects de ce problème, nous nous intéressons particulièrement, dans le cadre de notre sujet, à certaines de ses relaxations, qui ont aussi été étudiées pour apporter de nouvelles approches à la résolution du problème. Les structures combinatoires de ces relaxations peuvent être encapsulées dans des contraintes globales existantes en programmation par contraintes (PPC), ce qui nous motive à tester une approche basée sur des travaux récents sur les heuristiques de dénombrement en PPC. L'objectif de ce projet est d'améliorer la résolution du problème du voyageur de commerce en appliquant les densités de solution aux relaxations du problème. On pose l'hypothèse qu'une arête a très peu de chance d'appartenir à la solution optimale du problème si plusieurs relaxations retournent de faibles densités de solution pour cette arête et qu'on peut donc l'éliminer pour nettoyer le graphe d'entrée du problème. On évalue donc chaque arête en fonction de leur densité de solution pour chaque relaxation et on élimine les arêtes évaluées comme "mauvaises" par toutes les relaxations. Pour l'expérimentation, cet algorithme de pré-traitement sera appliqué à plusieurs exemplaires de TSPLIB, une bibliothèque d'exemplaires du problème de voyageur de commerce. On évaluera d'abord le temps de calcul de notre méthode. Enfin, on résoudra nos exemplaires élagués avec différents solveurs (concorde, Gurobi et IBM CP Optimizer) et on comparera les résultats obtenus à la résolution des exemplaires originels. L'élagage est efficace si le temps de résolution gagné en pré-traitant les exemplaires compense le temps de pré-traitement.