Résumé:
A new deflected subgradient algorithm is presented for computing a tighter
lower bound of the dual problem. These bounds may be useful in nodes evaluation in
a Branch and Bound algorithm to find the optimal solution of large-scale integer linear
programming problems. The deflected direction search used in this thesis is a convex combination of the Modified Gradient Technique and the Average Direction Strategy. In this context, we identify the optimal convex combination parameter allowing the deflected subgradient vector direction to form a more acute angle with the best direction towards an
optimal solution. The modified algorithm gives encouraging results for a selected symmetric travelling salesman problem (TSPs) instances taken from TSPLIB library
