Solution of large-scale symmetric travelling salesman problems

DOI10.1007/BF01586932zbMath0733.90047OpenAlexW2134092250WikidataQ96162457 ScholiaQ96162457MaRDI QIDQ810369

Olaf Holland, Martin Grötschel

Publication date: 1991

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

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

zbMATH Keywords

polyhedral combinatoricssymmetric travelling salesmancutting plane procedure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (61)

Generating subtour elimination constraints for the TSP from pure integer solutions ⋮ Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm ⋮ A branch-and-cut algorithm for vehicle routing problems ⋮ Problems of discrete optimization: challenges and main approaches to solve them ⋮ Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ Solving the max-cut problem using eigenvalues ⋮ On the polytope faces of the graph approximation problem ⋮ Ordered spatial sampling by means of the traveling salesman problem ⋮ ONLINE CAPACITY PLANNING FOR REHABILITATION TREATMENTS: AN APPROXIMATE DYNAMIC PROGRAMMING APPROACH ⋮ Routing problems: A bibliography ⋮ A hybrid approach for biobjective optimization ⋮ Solving real-world linear ordering problems using a primal-dual interior point cutting plane method ⋮ Packing Steiner trees: A cutting plane algorithm and computational results ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ The dragon war ⋮ Ideal polytopes and face structures of some combinatorial optimization problems ⋮ A learning based algorithm for drone routing ⋮ Some thoughts on combinatorial optimisation ⋮ The affine hull of the schedule polytope for servicing identical requests by parallel devices ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ A revisited branch-and-cut algorithm for large-scale orienteering problems ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ State partitioning based linear program for stochastic dynamic programs: an invariance property ⋮ Mixed-integer programming techniques for the minimum sum-of-squares clustering problem ⋮ Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times ⋮ Lexicographic local search and the \(p\)-center problem. ⋮ On facet-inducing inequalities for combinatorial polytopes ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Implementation of ensemble-based simulated annealing with dynamic load balancing under MPI ⋮ An improved column generation algorithm for minimum sum-of-squares clustering ⋮ Improved filtering for weighted circuit constraints ⋮ Record breaking optimization results using the ruin and recreate principle ⋮ Optimal partitioning of a data set based on the \(p\)-median model ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ Separating maximally violated comb inequalities in planar graphs ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ Point-to-point and multi-goal path planning for industrial robots ⋮ A cutting plane algorithm for the windy postman problem ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Branch and cut methods for network optimization ⋮ Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors ⋮ Strong IP formulations need large coefficients ⋮ Solving the family traveling salesman problem ⋮ Affinity propagation and uncapacitated facility location problems ⋮ Provably good solutions for the traveling salesman problem ⋮ A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning ⋮ The graphical relaxation: A new framework for the symmetric traveling salesman polytope ⋮ An optimality cut for mixed integer linear programs ⋮ Travelling on graphs with small highway dimension ⋮ The use of dynamic programming in genetic algorithms for permutation problems ⋮ Polyhedral techniques in combinatorial optimization I: Theory ⋮ Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems ⋮ Vehicle routing with stochastic demands and restricted failures ⋮ Searching for backbones -- an efficient parallel algorithm for the traveling salesman problem ⋮ A heuristic for the pickup and delivery traveling salesman problem ⋮ Computing in combinatorial optimization ⋮ An effective implementation of the Lin-Kernighan traveling salesman heuristic ⋮ Survey of facial results for the traveling salesman polytope ⋮ Genetic local search in combinatorial optimization ⋮ Relaxed tours and path ejections for the traveling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facet identification for the symmetric traveling salesman polytope
• An efficient algorithm for the minimum capacity cut problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• A cutting plane algorithm for minimum perfect 2-matchings
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• A Dynamic Programming Approach to Sequencing Problems
• A primal simplex variant for the maximum-flow problem
• Solving matching problems with linear programming
• Multi-Terminal Network Flows
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Odd Minimum Cut-Sets and b-Matchings
• Maximum matching and a polyhedron with 0,1-vertices
• 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
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Solution of large-scale symmetric travelling salesman problems