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 the present paper is a convex combination of the Modified Gradient Technique and the Average Direction Strategy. 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. MSC: 90C26, 90C10, 90C27, 90C06, Keywords: Integer linear programming, Subgradient method, Nonsmooth optimization, Travelling salesman problem

+More

convex combination parameter tighter lower bound of the dual branch and bound algorithm symmetric travelling salesman problem optimal solution of largescale integer linear programming modified gradient technique deflected subgradient algorithm deflected direction search tsplib library msc 90c26 90c10 90c27 90c06 keywords integer linear programming subgradient method nonsmooth optimization travelling salesman problem the average direction

Rachid Belgacem,Abdessamad Amir,.A new modified deflected subgradient method. 30 (4),.

Rachid Belgacem,Abdessamad Amir,"A new modified deflected subgradient method" 30

Rachid Belgacem,Abdessamad Amir,"A new modified deflected subgradient method"