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

DOI10.1016/j.ejor.2009.02.008zbMath1177.90402OpenAlexW2037882067MaRDI QIDQ1044139

Sim Kim Lau, M. Reza Zamani

Publication date: 10 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.02.008

zbMATH Keywords

heuristicsLagrangian relaxationtraveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (5)

A polarized adaptive schedule generation scheme for the resource-constrained project scheduling problem ⋮ Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem ⋮ Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory ⋮ A Lagrangian heuristic for capacitated single item lot sizing problems ⋮ A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem

Uses Software

• TSPLIB
• LKH
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lagrangean relaxation based heuristics for lot sizing with setup times
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• Estimating the Held-Karp lower bound for the geometric TSP
• The traveling salesman. Computational solutions for RSP applications
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems
• New lower bounds for the symmetric travelling salesman problem
• Accelerating the convergence of subgradient optimisation
• Lagrangean relaxation. (With comments and rejoinder).
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem
• TSPLIB—A Traveling Salesman Problem Library
• An improved branching rule for the symmetric travelling salesman problem
• A priority list based heuristic for the job shop problem
• Validation of subgradient optimization
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• A modified subgradient algorithm for Lagrangean relaxation

This page was built for publication: Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem