Problème du voyageur de commerce

[nico3004]

Bonjour,

Je dois réaliser un travail sur le problème du voyageur de commerce. Plus exactement, le résoudre de différentes manières, seulement je ne comprends absolument rien aux méthodes utilisées (il faut dire que je n'ai aucune base de tous les éléments utilisés pour comprendre ce dont on parle...).

Tout d'abord, est-ce que vous pourriez m'expliquer comment fonctionne l'algorithme "Branch and Bound", de séparation et d'évaluation ?
J'ai trouvé ce document (http://wwwens.uqac.ca/~rebaine/8INF806/techniquedebranchandboundcourshiver2005.pdf) que je trouve vulgarisant bien la méthode mais c'est encore incompréhensible pour moi...

[Sylviel]

L'idée très générale de Branch and Bound (je préviens j'écris au vol donc je ne cherche pas à montrer l'efficacité de la méthode, mais seulement le principe) :

Problème du sac à dos : maximiser la valeur d'un sac à dos de 20kg. Imaginons qu'il y a 3 objets :
A (poids : 1, valeur : 1)
B (poids : 3, valeur : 4)
C (poids : 6, valeur : 12)

Si le problème n'était pas à nombre entier (si on pouvait prendre des quantités réelles des objets) il suffirait de prendre le maximum de l'objet le plus dense en valeur, ie l'objet dont la valeur pour un poids unité est maximum, ici mon objet C. --> tu remarques que sans la contrainte de nombres entier la solution se fait très facilement (de manière générale il s'agit d'optimisation linéaire, domaine très bien connu des mathématiques).

Donc maintenant comment procéder pour trouver la solution optimale en nombre entier ? Et bien on va commencer par s'intéresser à un objet, par exemple le plus dense, et se demander combien on en met. 4 possibilités :
0, 1, 2, 3.

On calcule une solution possible (S): 2A+3C qui a pour valeur 2+3*12 = 38

Maintenant si on prends 2C seulement, et qu'on relâche la contrainte de nombre entier sur les autres variables on a : 2*12 + 8*(4/3) < 38, donc comme la meilleure solution possible en prenant seulement 2C est moins bonne que la solution optimale en nombre réel, qui est moins bonne que S pas la peine de se casser la tête ! On peux éliminer toutes les possibilités avec 2C.

Pour résumer :
* j'ai fait un arbre de possibiliités (sans l'écrire, heureusement !)
--> Choisir le nombre de C, puis le nombre de B puis le nombre de A
* J'ai trouvé une "bonne solution"
* J'ai majoré (puisqu'on est dans un problème de maximisation) la meilleure solution d'un sous arbre
* Et montré que cette borne est moins bonne qu'une vraie solution déjà obtenue
--> pas la peine d'explorer le sous arbre !

Bon je sais que ce n'est pas évident la première fois, donc prends le temps de relire mon message avant de poser une question.

[nico3004]

Merci =)
Je pense que je commence à comprendre plus ou moins...
Cependant dans le document dont j'ai donné le lien, on donne un exemple pour le voyageur de commerce, avec une manière de calculer la borne inférieure. Seulement, je ne comprends pas à quoi correspondent les chiffres... J'essaie de les associer, mais ne vois vraiment pas comment est-ce qu'ils ont appliqué la théorie dont ils parlent juste au-dessus (avec "arc - vi + arc - vi"...)