Méthode par sépation et évaluation : problème du voyageur de commerce
Il s'agit de déterminer un cycle hamiltonien aussi appelé tour, de plus petit poids dans un graphe complet valué par des entiers positifs ou nuls.
Le programme est lancé en indiquant sur la ligne de commande :
- le nom de l'exécutable ;
- le fichier contenant le codage du graphe ;
- 0 si on ne veut pas utiliser la relaxation lagrangienne ou bien 1 si on veut utiliser celle-ci ;
- la valeur initiale du paramètre alpha (voir le cours) ;
- le nombre d'itérations dans la recherche du maximum de la fonction duale ;
- une borne qui doit être un majorant de la solution.
Exemple :
tsp g50 0 : il s'agit de trouver le plus petit tour dans le graphe g50 sans utiliser la relaxation lagrangienne.
tsp g50 1 1.5 10 5000 : il s'agit de trouver le plus petit tour dans le graphe g50 en utilisant la relaxation lagrangienne, avec la valeur initiale de alpha qui vaut 1.5, en faisant toujours 10 itérations de la relaxation lagrangienne avec une borne initiale de 5000.
Vous pouvez télécharger :
- Un Makefile ;
- un fichier d'en-tête tsp.h
- un fichier contenant l'essentiel du programme sauf ce qui concerne la relaxation lagrangienne, tsp.c
- un fichier à compléter qui contient ce qui concerne la relaxation lagrangienne, relaxation.c
Quelque graphes pour faire des tests (la première ligne donne l'ordre, la deuxième un majorant des poids, les lignes suivantes la demi-matrice triangulaire des poids) :
Travail à rendre
Chaque élève rendra à l'enseignant une feuille de bilan.
Premier temps : après avoir téléchargé l'ensemble des fichiers et avoir compilé, tester le programme sur chacun des graphes fournis (par exemple, avec la commande : tsp g10 0 ). Quand le résultat se fait trop attendre, on interrompra l'exécution. A la fin de l'exécution, le programme indique le nombre de noeuds traités dans l'arborescence de recherche. Dans la feuille de bilan, noter, pour chacun des graphes dont l'exécution a pu se faire en un temps raisonnables, ce nombre de noeuds.
Deuxième temps : compléter la fonction relaxation dans le fichier relaxation.c.
Troisième temps : tester le programme complété sur chacun des graphes fournis. On cherchera à régler les paramètres (surtout alpha_initial et nombre d'itérations) pour augmenter l'efficacité. On indiquera pour chacun des graphes le nombre obtenu de noeuds minimum et les valeurs correspondants des paramètres (on observera que les bonnes valeurs de alpha sont beaucoup plus petites pour les tout petits graphes que pour les gros). Faire une petite étude, sur un des graphes au choix, de l'influence du choix de alpha, du choix du nombre d'itérations et du choix de la borne.
Irene Charon
Last modified: Wed Dec 1 14:52:12 CET 2010