Lagrangian object relaxation neural network for combinatorial optimization problems

We propose a Lagrangian object relaxation technique that can obtain a more near-optimal solution for the traveling salesman problem (TSP). It consists of two stages. First, a feasible solution is calculated and second, a more near-optimal solution is calculated by a Hopfield neural network (HNN). The Lagrangian object relaxation technique can help the HNN escape from the local minimum by correcting Lagrangian multipliers. The Lagrangian object relaxation neural network is analyzed theoretically and evaluated experimentally through simulating the TSP. The simulation results based on some TSPLIB benchmark problems show that the proposed method can find 100% valid solutions which are near-optimal solutions.