Embedding learning capability in Lagrangean relaxation: An application to the travelling salesman problem

This paper presents an effective procedure that finds lower bounds for the travelling salesman problem based on the 1-tree using a learning-based Lagrangian relaxation technique. The procedure can dynamically alter its step-size depending upon its previous iterations. Along with having the capability of expansion–contraction, the procedure performs a learning process in which Lagrange multipliers are influenced by a weighted cost function of their neighbouring nodes. In analogy with simulated annealing paradigm, here a learning process is equivalent to escaping local optimality via exploiting the structure of the problem. Computational results conducted on Euclidean benchmarks from the TSPLIB library show that the procedure is very effective.