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

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.