Solution of large-scale symmetric travelling salesman problems
From MaRDI portal
Publication:810369
DOI10.1007/BF01586932zbMATH Open0733.90047OpenAlexW2134092250WikidataQ96162457 ScholiaQ96162457MaRDI QIDQ810369FDOQ810369
Authors: Martin Grötschel, Olaf Holland 
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
Recommendations
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- On the solution of traveling salesman problems
- scientific article; zbMATH DE number 1947373
- Exact solution of large-scale, asymmetric traveling salesman problems
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- Geometric algorithms and combinatorial optimization
- A Dynamic Programming Approach to Sequencing Problems
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- The ellipsoid method and its consequences in combinatorial optimization
- 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
- Solving matching problems with linear programming
- Title not available (Why is that?)
- Maximum matching and a polyhedron with 0,1-vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
- Multi-Terminal Network Flows
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Facet identification for the symmetric traveling salesman polytope
- Odd Minimum Cut-Sets and b-Matchings
- An efficient algorithm for the minimum capacity cut problem
- Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
- A cutting plane algorithm for minimum perfect 2-matchings
- A primal simplex variant for the maximum-flow problem
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- A man-machine approach toward solving the traveling salesman problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (87)
- Separating maximally violated comb inequalities in planar graphs
- Deep clustering of the traveling salesman problem to parallelize its solution
- Point-to-point and multi-goal path planning for industrial robots
- On the polytope faces of the graph approximation problem
- Title not available (Why is that?)
- Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
- Strong IP formulations need large coefficients
- Affinity propagation and uncapacitated facility location problems
- Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors
- Deriving compact extended formulations via LP-based separation techniques
- Travelling on graphs with small highway dimension
- A learning based algorithm for drone routing
- A revisited branch-and-cut algorithm for large-scale orienteering problems
- On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
- State partitioning based linear program for stochastic dynamic programs: an invariance property
- The affine hull of the schedule polytope for servicing identical requests by parallel devices
- On facet-inducing inequalities for combinatorial polytopes
- Computing in combinatorial optimization
- Implementation of ensemble-based simulated annealing with dynamic load balancing under MPI
- ONLINE CAPACITY PLANNING FOR REHABILITATION TREATMENTS: AN APPROXIMATE DYNAMIC PROGRAMMING APPROACH
- Genetic local search in combinatorial optimization
- Some thoughts on combinatorial optimisation
- The use of dynamic programming in genetic algorithms for permutation problems
- Chained Lin-Kernighan for large traveling salesman problems
- A branch-and-cut algorithm for vehicle routing problems
- Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
- Generating subtour elimination constraints for the TSP from pure integer solutions
- 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
- Computing compatible tours for the symmetric traveling salesman problem
- Combinatorial algorithms in concorde
- A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
- Solving a semidefinite relaxation of the traveling salesman problem.
- Solving the max-cut problem using eigenvalues
- Optimal partitioning of a data set based on the \(p\)-median model
- Improved filtering for weighted circuit constraints
- An optimality cut for mixed integer linear programs
- A cutting plane procedure for the travelling salesman problem on road networks
- Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Provably good solutions for the traveling salesman problem
- Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems
- Tabu search performance on the symmetric travelling salesman problem
- Solving the family traveling salesman problem
- An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem
- The traveling salesman problem: An overview of exact and approximate algorithms
- Vehicle routing with stochastic demands and restricted failures
- An improved column generation algorithm for minimum sum-of-squares clustering
- Improved large-step Markov chain variants for the symmetric TSP
- Polyhedral techniques in combinatorial optimization I: Theory
- Title not available (Why is that?)
- A heuristic for the pickup and delivery traveling salesman problem
- Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
- Relaxed tours and path ejections for the traveling salesman problem
- Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem
- The dragon war
- Branch-and-cut approach to a variant of the traveling salesman problem
- Certification of an optimal TSP tour through 85,900 cities
- On the solution of the traveling salesman problem once again
- Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies
- Title not available (Why is that?)
- A hybrid approach for biobjective optimization
- Ordered spatial sampling by means of the traveling salesman problem
- Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times
- Ideal polytopes and face structures of some combinatorial optimization problems
- Searching for backbones -- an efficient parallel algorithm for the traveling salesman problem
- Routing problems: A bibliography
- Record breaking optimization results using the ruin and recreate principle
- Travelling salesman problem tools for microcomputers
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- Branch and cut methods for network optimization
- Solution of a Large-Scale Traveling-Salesman Problem
- Title not available (Why is that?)
- An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
- Lexicographic local search and the \(p\)-center problem.
- Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
- An approximation algorithm for the clustered path travelling salesman problem
- An approximation algorithm for the clustered path travelling salesman problem
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- Mixed-integer programming techniques for the minimum sum-of-squares clustering problem
- Nonoptimal Edges for the Symmetric Traveling Salesman Problem
- Deriving compact extended formulations via LP-based separation techniques
- Packing Steiner trees: A cutting plane algorithm and computational results
- Survey of facial results for the traveling salesman polytope
- A cutting plane algorithm for the windy postman problem
- Exploiting planarity in separation routines for the symmetric traveling salesman problem
- Problems of discrete optimization: challenges and main approaches to solve them
This page was built for publication: Solution of large-scale symmetric travelling salesman problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810369)
