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

DOI10.1016/0167-6377(90)90033-2zbMATH Open0696.90078OpenAlexW2009084435MaRDI QIDQ911484FDOQ911484

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

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

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)

Cites Work

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

Cited In (3)

• Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
• Title not available (Why is that?)
• 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)