Résumé:
Un nouvel algorithme de sous-gradient dévié est présenté pour calculer une
borne inférieure du problème dual. Ces bornes peuvent être utiles, dans l’évaluation des
nœuds dans un l’algorithme ’Branch and Bound’, pour trouver la solution optimale des problèmes de programmation linéaire en nombre entier à grande taille. La direction de recherche
déviée utilisée dans cette thèse est une combinaison convexe de la technique de gradient modifié et de la stratégie de direction moyenne. Dans ce contexte, nous identifions le paramètre
de combinaison convexe optimal permettant à la direction du vecteur sous-gradient dévié
de former un angle plus aigu avec la meilleure direction vers une solution optimale. L’algorithme modifié donne des résultats encourageants pour des instances de problèmes de
voyageur de commerce symétrique (TSPs) sélectionnés depuis la base de données TSPLIB.
