Theoretical and numerical contribution for solving traveling salesman problem
Contribution théorique et numérique à la résolution du problème du Voyageur de Commerce
Résumé
This dissertation is divided into two part, a theoretical one deals with the traveling salesman polytope, the convex hull of hamiltonian cycles, and a more numerical one in which we try to improve the ``Branch and Cut'' method for traveling salesman problem. The theoretical contribution consists in proving that the class of domino inequalities is facet inducing for the traveling salesman polytope. The numerical one deals with the separation outside the template paradigm by studying cut generation from small graphs obtained from a bigger one by shrinking minimum cuts. Finally branching is studied in order to make more robust this part of "Branch and Cut''.
Ce travail de thèse comporte deux composantes, l'une théorique sur l'enveloppe convexe des cycles hamiltoniens, aussi appelée polytope du Voyageur de Commerce, et une autre plus numérique sur l'amélioration de la résolution exacte par la méthode "Branch & Cut'' du problème du Voyageur de Commerce. L'apport théorique consiste en la démonstration qu'une classe d'inéquations, les contraintes de domino, induisent des facettes du polytope du Voyageur de Commerce. L'aspect numérique aborde la séparation hors paradigme de classe en proposant la génération de coupes à partir de la contraction d'un grand graphe en un plus petit à l'aide de la représentation en cactus des coupes minimum. Enfin diverses pistes ont été étudiées pour rendre l'étape de branchement plus robuste.
Loading...