A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem

DOI10.1016/0167-6377(90)90033-2zbMath0696.90078OpenAlexW2009084435MaRDI QIDQ911484

Marshall L. Fisher, Kavindra Malik

Publication date: 1990

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(90)90033-2

zbMATH Keywords

subgradient methoddual ascent1-tree relaxationout of kiltersymmetric traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05)

Related Items (1)

Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies

Cites Work

• Unnamed Item
• Unnamed Item
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Applications of Path Compression on Balanced Trees
• A Dynamic Programming Approach to Sequencing Problems
• A dual ascent approach for steiner tree problems on a directed graph
• A Dual-Based Procedure for Uncapacitated Facility Location
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Validation of subgradient optimization
• Solution of a Large-Scale Traveling-Salesman Problem
• A man-machine approach toward solving the traveling salesman problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem