Solution of large-scale symmetric travelling salesman problems
From MaRDI portal
Publication:810369
DOI10.1007/BF01586932zbMath0733.90047WikidataQ96162457 ScholiaQ96162457MaRDI QIDQ810369
Martin Grötschel, Olaf Holland
Publication date: 1991
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
90C35: Programming involving graphs or networks
65K05: Numerical mathematical programming methods
90C06: Large-scale problems in mathematical programming
52B12: Special polytopes (linear programming, centrally symmetric, etc.)
90C10: Integer programming
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
Provably good solutions for the traveling salesman problem, Polyhedral techniques in combinatorial optimization I: Theory, Branch and cut methods for network optimization, The dragon war, Optimal partitioning of a data set based on the \(p\)-median model, The traveling salesman problem: An overview of exact and approximate algorithms, A cutting plane algorithm for the windy postman problem, The use of dynamic programming in genetic algorithms for permutation problems, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Searching for backbones -- an efficient parallel algorithm for the traveling salesman problem, Genetic local search in combinatorial optimization, A branch-and-cut algorithm for vehicle routing problems, Some thoughts on combinatorial optimisation, Lexicographic local search and the \(p\)-center problem., A heuristic for the pickup and delivery traveling salesman problem, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Survey of facial results for the traveling salesman polytope, Relaxed tours and path ejections for the traveling salesman problem, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, An optimality cut for mixed integer linear programs, Solving the max-cut problem using eigenvalues, Routing problems: A bibliography, 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, Ideal polytopes and face structures of some combinatorial optimization problems, Implementation of ensemble-based simulated annealing with dynamic load balancing under MPI, Record breaking optimization results using the ruin and recreate principle, 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), A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning, Point-to-point and multi-goal path planning for industrial robots, Vehicle routing with stochastic demands and restricted failures
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