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

DOI10.1016/0167-6377(90)90033-2MaRDI QIDQ911484zbMATH OpenOpenAlexFDO

Authors Kavindra Malik, Marshall L. Fisher

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

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

Recommendations

• The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
• SELECTION OF RELAXATION PROBLEMS FOR A CLASS OF ASYMMETRIC TRAVELING SALESMAN PROBLEM INSTANCES
• Branch-and-bound algorithm for symmetric travelling salesman problem
• A study of the parameters of branch-and-bound algorithms for solving the symmetric traveling salesman problem
• Exact solution of large-scale, asymmetric traveling salesman problems

Cites work

• scientific article; zbMATH DE number 3559294 (Why is no real title available?)
• scientific article; zbMATH DE number 3577030 (Why is no real title available?)
• A Dual-Based Procedure for Uncapacitated Facility Location
• A Dynamic Programming Approach to Sequencing Problems
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• A dual ascent approach for steiner tree problems on a directed graph
• A man-machine approach toward solving the traveling salesman problem
• Applications of Path Compression on Balanced Trees
• Solution of a Large-Scale Traveling-Salesman Problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Validation of subgradient optimization

Cited in

(3)

• Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
• scientific article; zbMATH DE number 4167859 (Why is no real title available?)
• SELECTION OF RELAXATION PROBLEMS FOR A CLASS OF ASYMMETRIC TRAVELING SALESMAN PROBLEM INSTANCES

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911484)