paprika.idref.fr paprika.idref.fr data.idref.fr data.idref.fr Documentation Documentation
Identifiant pérenne de la notice : 226721345Copier cet identifiant (PPN)
Notice de type Notice de regroupement

Point d'accès autorisé

Contribution théorique et numérique à la résolution du problème du voyageur de commerce

Variante de point d'accès

Theoretical and numerical contributions for solving the traveling salesman problem
[Notice de regroupement]

Information

Langue d'expression : français
Date de parution :  2003

Notes

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.


Notices d'autorité liées

... Références liées : ...