New lower bounds for the symmetric travelling salesman problem

DOI10.1007/BF01589105zbMath0682.90093OpenAlexW2081570649MaRDI QIDQ1824572

Matteo Fischetti, Paolo Toth, Giorgio Carpaneto

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01589105

zbMATH Keywords

lower boundsreduced costsrandomly generated test problemsadditive bounding proceduresShortest Spanning TreeSymmetric Travelling Salesman Problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05)

Related Items

An exact algorithm for the capacitated shortest spanning arborescence, Routing problems: A bibliography, A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program, An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading, An additive bounding procedure for the asymmetric travelling salesman problem, The traveling salesman problem: An overview of exact and approximate algorithms, A gene-pool based genetic algorithm for TSP, Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem, An effective implementation of the Lin-Kernighan traveling salesman heuristic

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• An additive bounding procedure for the asymmetric travelling salesman problem
• An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
• A branch and bound algorithm for the multiple depot vehicle scheduling problem
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• A restricted Lagrangean approach to the traveling salesman problem
• Finding optimum branchings
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Optimum branchings
• The Shortest Hamiltonian Chain of a Graph
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II