Solution of large-scale symmetric travelling salesman problems

DOI10.1007/BF01586932zbMath0733.90047OpenAlexW2134092250WikidataQ96162457 ScholiaQ96162457MaRDI QIDQ810369

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 combinatorics symmetric travelling salesman cutting 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

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