Using Information from Solution Densities of Relaxations in Solving Variants of the Traveling Salesman Problem

The traveling salesman problem (TSP) is a very widely studied routing problem that aimsat finding a minimum length Hamiltonian tour in a graph. The problem in itself is NP-hard, and often used as a research focus in the development of optimization techniques. Several variants exist for the problem, adding time constraints or asymmetric distances in the graph. The goal of this subject is to develop reduction methods to simplify the resolution of these TSP-like problems.Our main focus is using relaxations of the problems in order to get relevant information on good variable-value assignments. We present several relaxations, i.e., easier related problems, and the corresponding information, called solution density. This document compiles computation methods and less time-consuming approximation for these solution densities. We introduce methods to use this information to simplify the resolution: how to select good arcs, reduce the domains of the time variables and infer partial orders. We test these approaches on several solvers from two different solving paradigms, namely Constraint Programming and Mixed-Integer Programming and report experimental results on usual benchmarks.

Résumé

Le sujet de cette maîtrise est la famille de problèmes liée au Voyageur de Commerce. Ce problème NP-diÿcile, rendu célèbre pour ses nombreuses applications et pour la variété des améliorations dans le domaine de l'optimisation apparues en l'étudiant, vise à déterminer un cycle hamiltonien de poids minimum dans un graphe. Plusieurs variantes existent, qui incluent des contraintes additionnelles. En particulier, ce sujet se concentre sur l'introduction d'une asymmétrie des coûts et l'ajout de contraintes temporelles. Au cours de ce projet, nous cherchons à développer des méthodes d'aide à la résolution de ces variantes, basées sur le concept de densités de solutions. Nous utilisons l'information obtenue en résolvant des problèmes similaires et plus faciles. Pour ce faire, plusieurs relaxations sont présentées ainsi que la façon de calculer les densités correspondantes. L'objectif est d'accélérer la résolution par des modèles de Programmation par Contraintes et de Programmation en Nombres Entiers, deux paradigmes de modélisation et résolution de problèmes. Dans ces modèles, nos densités de solutions peuvent être interprétées comme des probabilités qu'une valeur particulière soit a˙ectée à une variable.