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

ABRACTS : The Traveling Salesman Problem is a combinatorial optimization problem, which, broadly speaking, consists of visiting a certain number n of cities, by passing through each city exactly once and by traveling the shortest possible distance. This problem is very prominent in research, as a representative of the NP-hard class of problems and as a problem with applications in various areas, including routing, networking and scheduling. Nowadays, integer programming methods dominate the landscape of TSP solvers, with the state-of-art solver concorde. As part of the efforts to solve the TSP, several of its relaxations have been studied, for computing lower bounds or domain filtering. Since these relaxations can provide insight on the combinatorial structure of the problem, we believe recent work in Constraint Programming concerning counting-based branching heuristics can bring new effective methods of using these relaxations. In this Master's thesis, we present an approach to the traveling salesman problem which exploits cost-based solution densities from counting-based search. we propose a method for eliminating edges from the input graph of TSP instances in pre-processing, by using the solution densities from relaxations of the TSP to determine promising edges. Solution densities from different relaxations can also be combined for branching in a constraint programming solver. The efficiency and robustness of our pre-processing algorithm is evaluated by applying it to instances from TSPLIB and comparing the time to solve them with that of the original complete instances. We consider various solvers in our experimentation, namely the IBM CP Optimizer, concorde and Gurobi.

Résumé

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.