Identifiant pérenne de la notice : 226721345
Notice de type
Notice de regroupement
Note publique d'information : 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
and 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 debranchement plus robuste.